Counting subsets with sum not exceeding some limit 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 &lt;= n &lt;= 30
1 &lt;= array[i] &lt;= 1e9
0 &lt;= limit &lt;= 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&lt;int, int&gt; dp;

for (int element_idx = 0; element_idx &lt; i_size; ++element_idx) {

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

  for (std::pair&lt;int, int&gt; &amp;sum_count : dp) {
    if (sum_count.first + arr[element_idx] &lt;= 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.
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: 


Let's split the array into two even parts (almost even if n is odd).
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)})\$.
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] &lt;= S for a given value of S.
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&amp; 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)\$.