Counting subsets with sum not exceeding some limit

Question

I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the following DP relations

#number of ways to get sum using subsets of {1, 2, ..., i}
dp[i][sum] += dp[i - 1][sum]            #not using element i
dp[i][sum + array[i]] += dp[i - 1][sum] #using element i 

Constraints:

1 <= n <= 30
1 <= array[i] <= 1e9
0 <= limit <= 1e9
Time: 1s
Memory: 64 Mb

At first I considered using plain array( or std::array, whatever) but an array dp[30][1e9 + 1] can't be allocated on stack and heap allocation would be too expensive given time limit of 1 second. I came up with the following implementation using std::unordered_map:

std::unordered_map<int, int> dp;

for (int element_idx = 0; element_idx < i_size; ++element_idx) {

  if (arr[element_idx] > limit) {
    continue;
  }
  std::unordered_map<int, int> new_sums;
  new_sums[arr[element_idx]] = 1;
  if (!element_idx) {
    dp = std::move(new_sums);
    continue;
  }
  for (std::pair<int, int> &sum_count : dp) {
    new_sums[sum_count.first] += sum_count.second;
  }

  for (std::pair<int, int> &sum_count : dp) {
    if (sum_count.first + arr[element_idx] <= limit) {
      new_sums[sum_count.first + arr[element_idx]] += sum_count.second;
    }
  }
  dp = std::move(new_sums);
}

The problem it that this implementation runs into a memory limit error. Moreover, my computer just freezes if the input is 30 distinct 6-, 7-digit integers. I am pretty sure there is nothing wrong with my algorithm and the only problem my poor algorithm implementation experience and C++ knowledge.

Answer 1

The problem is actually with your algorithm, not with your C++ code. The time complexity of your solution is \$O(2^n \times \text{polynomial}(n))\$, which is too much for the given constraints.

You can use the meet-in-the-middle technique to make it \$O(2^{(n/2)} \times \text{polynomial}(n))\$, which is good enough.

The idea is as follows:

1. Let's split the array into two even parts (almost even if n is odd).
2. Let's generate all sums in the first in and in the second part and store them in vectors as and bs. This part requires \$O(2^{(n/2)})\$.
3. Now the problem is simpler: given two vectors A and B, compute the number of pairs of valid indices i and j such that as[i] + bs[j] <= S for a given value of S.

4. Let's sort bs and iterate over as. As bs is increasing, all valid elements of bs for a given element a from as are in some prefix of B. We can find its size as std::upper_bound(bs.begin(), bs.end(), a) - bs.begin()
   That is, this part of this solution looks like:

   for (const auto& a : as) {
       result += std::upper_bound(bs.begin(), bs.end(), a) - bs.begin();
   }
   

The total time complexity is \$O(2^{(n/2)} \times \log(2^{(n/2)}) = O(2^{(n/2)} \times n)\$.