USACO 2.2 Subset Sum

It’s tempting to solve this using brutal force search like dfs:

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <bitset>
#include <set>

using namespace std;

int result;
int expected;
int N;
set<unsigned long> st;
bitset<32> bset;

void dfs(int sum, int index) {
    if (sum == expected && !st.count(bset.to_ulong())) {
        st.insert(bset.to_ulong());
        ++result;
    }

    if (sum > expected) return;

    for (int i = index; i <= N ; ++i) {
        bset.set(i);
        dfs(sum + i, i + 1);
        bset.flip(i);
    }
}

int main() {
    ifstream fin("subset.in");
    ofstream fout("subset.out");
    bset.reset();
    fin >> N;
    expected = (N + 1) * N / 2;
    if (expected % 2)
        return 0;

    expected /= 2;
    dfs(0, 1);
    fout << result / 2 << endl;
}

This solution however does not pass all tests, which has a time limit of 1 sec and a space limit of 16MB. The reason is the simple search will yield an exponential algorithm, given the state that we are about to explore is as much as 2^N, where N could be as large as 39. That said, it might be possible to optimize the search based algorithm using data structures that provides very optimized memory foot print with fast lookup, but I’ve not yet found such a data structure that satisfy the constraints.

Thinking from another perspective, the set / sum exhibits recursive nature and there are sub problems when solving each set partition, so dynamic programming is here for rescue:

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
int expected;
int result;

int main() {
    ifstream fin("subset.in");
    ofstream fout("subset.out");
    fin >> N;
    vector<vector<unsigned long long>> dp(40, vector<unsigned long long>(800, 0));
    expected = (N + 1) * N / 2;
    if (expected % 2) {
        fout << 0 << endl;
        return 0;
    }

    expected /= 2;

    cout << "expected :" << expected << endl;

    for (int i = 0; i <= N; ++i) {
        dp[i][0] = 1;
    }
    cout << N << " " << expected << endl;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= expected; ++j) {
            dp[i][j] += dp[i - 1][j];
            if (i <= j) {
                dp[i][j] += dp[i - 1][j - i];
            }
        }
    }
    fout << dp[N][expected] / 2 << endl;
}