Count subset sums more efficiently

Правка en2, от The-2024ECPCwinner, 2023-06-07 10:25:03

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) .


  Rev. Язык Кто Когда Δ Комментарий
en2 Английский The-2024ECPCwinner 2023-06-07 10:25:03 10
en1 Английский The-2024ECPCwinner 2023-06-07 10:24:26 868 Initial revision (published)