Count subset sums more efficiently

Revision en1, by The-2024ECPCwinner, 2023-06-07 10:24:26
In the last Codeforces Round 878 (Div. 3)  I was trying to solve problem B using count subset sum function .[submission: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) .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English The-2024ECPCwinner 2023-06-07 10:25:03 10
en1 English The-2024ECPCwinner 2023-06-07 10:24:26 868 Initial revision (published)