The-2024ECPCwinner's blog

Count subset sums more efficiently
By The-2024ECPCwinner, history, 19 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

Comments Comments (1)
| Write comment?
»
19 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

→ Reply