UVA - 12911 Subset Sum

Intuition

If we try to use brute-force algorithm to solve this problem, we will find O(2^n) in complexity. But, since max of n is 40, it’s too long to pass. Namely, $2^{40}\sim 10^{12}$. Also, although it looks like a dynamic programming problem, it’s not working either.

Surprisingly, it’s easier than I thought. All we have to do is divide it into half. That way, the complexity will became $2^{n/2}+2^{n/2}$, which has a maximum of $2^{20}+2^{20}=2^{21}\sim 2*10^{6}$.

But, that only include time of 2 brute-force divide. We have to also conquer it. There’s the procedure,

1. devide all numbers into nums1, nums2 equaly
2. nums1 -> map1 (possible sum, combinations), also, nums2 -> map2.
3. for each map1 value, find a value in map2 that satisfy val1 + val2 = target.

combinations

how many combinations in nums1 can construct that sum

Therefore, we get the total complexity is $Time=2*2^{n}*lg(2^n)+2^{n}*lg(2^n)={3}*2^{n}*n$ , where n has a maximum of 20. Namely, we obtain the worse case run time is
$$O_w({3}*2^{n}*n)={3}*2^{20}*20\sim {6}*10^7$$

Sample Code:

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n, target, res;

void build_mp(vector<ll> &nums, unordered_map<ll, ll> &mp)
{
    ll m = 1 << nums.size();
    for (ll i = 0; i < m; i++)
    {
        ll sum = 0;
        for (ll j = 0; j < nums.size(); j++)
            if ((1 << j) & i)
                sum += nums[j];
        mp[sum]++;
    }
}

int main()
{
    while (cin >> n >> target)
    {
        ll bpt = n / 2;
        res = 0;
        vector<ll> nums1(bpt), nums2(n - bpt);
        for (int i = 0; i < nums1.size(); i++)
            cin >> nums1[i];
        for (int i = 0; i < nums2.size(); i++)
            cin >> nums2[i];
        unordered_map<ll, ll> mp1, mp2;
        build_mp(nums1, mp1);
        build_mp(nums2, mp2);
        for (auto it : mp1)
        {
            ll goal = target - it.first;
            if (mp2.find(goal) != mp2.end())
                res += it.second * mp2[goal];
        }
        // when target == 0, (none) set cannot exist, while (0,0) is okay.
        if (target == 0)
            res--;
        cout << res << "\n";
    }
}