Ledea_Tharwt's blog

By Ledea_Tharwt, history, 3 months ago, In English

In the last Codeforces Round 878 (Div. 3) I was trying to solve problem B using count subset sum function . 208751901

By generating a vector containing all the powers of 2 ,and search for how many different subsets such that their sum is less than or equal value k. It uses backtracking to explore all possible combinations of including or excluding each element in the subset. But as expected it gives me TLE as its time complexity is equal to (2^N) Each recursive call further branches into two recursive calls until the base cases are reached , This doubling effect results in an exponential time complexity. I am not exactly asking about problem B as I have already solved it . I am asking about how to implement this function with less time complexity using DP maybe O(n) , O(n^2) or even O(n^3) .

  • Vote: I like it
  • -12
  • Vote: I do not like it

3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by Ledea_Tharwt (previous revision, new revision, compare).

3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have heard about some way to count subsets but using python DP in only O(n*k) , I think this would help :

def countsub(nums, k): n = len(nums) dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):
    dp[i][0] = 1

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if nums[i - 1] > j:
            dp[i][j] = dp[i - 1][j]
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]

count = sum(dp[n])
return count
3 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

answer: no

reason: subset sums is (weakly, but still) NP-Hard ($$$O(2^{n/2})$$$ is possible tho)

or maybe yes if u prove $$$P=NP$$$ but who would even prove it so soon