3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ When dealing with asignements or code competitions, check numerical limits : ints are far to small here, you should use longs or long longs \$\endgroup\$ – Yk Cheese Sep 20 '17 at 19:52
  • \$\begingroup\$ Do I understand this correctly? For each n you want to know how many different subsets S of {1, … n} you can find such that that the sum of elements does not exceed the limit, i.e. sum(S) <= limit? So in total it is size({S subset {1, …, n} if sum(S) <= limit})? \$\endgroup\$ – Martin Ueding Sep 20 '17 at 20:00
  • \$\begingroup\$ I am the original poster and I forgot to log in before making the post. 1) @Yk Cheese , int is enough here because every time I add a value to map I check whether it is less than or equal to limit which, in its turn, is always less than or equal to 1e9 which fits in int on both my and my online judge's machines. Thanks for your advice anyway! 2) @Martin Ueding size({S subset {1, …, n} if sum(S) <= limit}) is indeed what I am looking for. The part 'for each n' is unnecessary though. \$\endgroup\$ – Atin Sep 20 '17 at 20:12
  • \$\begingroup\$ @YkCheese reply from OP (which may get deleted as answer): "@Yk Cheese , int is enough here because every time I add a value to map I check whether it is less than or equal to limit which, in its turn, is always less than or equal to 1e9 which fits in int on both my and my online judge's machines. Thanks for your advice anyway!" \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 20 '17 at 20:18
  • \$\begingroup\$ @MartinUeding reply from OP (which may get deleted as answer): "size({S subset {1, …, n} if sum(S) <= limit}) is indeed what I am looking for. The part 'for each n' is unnecessary though." \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 20 '17 at 20:19
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I am really sorry I am writing what is meant to a be a comment as an answer again(I am the OP) but I have to comment that almost everything about @kraskevich's answer is perfect. It helped me solve the task and it forced me into another approach which is sort of discovery for me and hence satisfying. The only mistake I'd like to point out is that the binary search(std::upper_bound) should really look for limit - a instead of a. Unfortunately, I can't neither upvote nor mark it an a solution \$\endgroup\$ – Atin Sep 21 '17 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.