When exhaustive search becomes infeasible due to exponential state growth, splitting the problem into two halves and combining partial results can drastically cut runtime. This method explores subsets independently in each half, then merges them efficiently using sorting and binary search or lookup structures.

Problem: Hockey Championshipp Ticket Combinations (N ≤ 40, M = budget)

A naive enumeration of all 2^N selection is too slow. Split the N items into two groups of sizes roughly ceil(N/2) and floor(N/2). Enumerate all achievable sums in each group via depth-first traversal.

First group enumeration:

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

vector<ll> sumsA, sumsB;
vector<ll> itemsA, itemsB;
ll limit;

void build_sums(const vector<ll>& arr, vector<ll>& out, int idx, ll cur) {
    if (idx == arr.size()) {
        out.push_back(cur);
        return;
    }
    build_sums(arr, out, idx + 1, cur);
    build_sums(arr, out, idx + 1, cur + arr[idx]);
}

int main() {
    int n;
    cin >> n >> limit;
    int split = (n + 1) / 2;
    itemsA.resize(split);
    itemsB.resize(n - split);
    for (int i = 0; i < split; i++) cin >> itemsA[i];
    for (int i = 0; i < n - split; i++) cin >> itemsB[i];

    build_sums(itemsA, sumsA, 0, 0);
    build_sums(itemsB, sumsB, 0, 0);

    sort(sumsB.begin(), sumsB.end());

    ll total = 0;
    for (ll sa : sumsA) {
        ll rem = limit - sa;
        auto it = upper_bound(sumsB.begin(), sumsB.end(), rem);
        total += (it - sumsB.begin());
    }
    cout << total << endl;
    return 0;
}

The first half's sums are generated without sorting because we binary-search the second half's sorted sums for each candidate from the first half, counting how many fit within the remaining budget.

Problem: Balanced Cow Subsets (N up to 20, three-state per item)

Each number may go to left set, right set, or none. Naive 3^N is impractical. Use meet-in-the-middle to track difference between sums of the two chosen sets. A valid balanced selection corresponds to zero difference across both halves.

Initial direct approach (slow):

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

int n, arr[55];
map<int, vector<int>> diffLeft;
bool seen[1 << 20];

void explore_left(int idx, int diff, int mask) {
    if (idx > n / 2) {
        diffLeft[diff].push_back(mask);
        return;
    }
    explore_left(idx + 1, diff, mask);
    explore_left(idx + 1, diff + arr[idx], mask | (1 << (idx - 1)));
    explore_left(idx + 1, diff - arr[idx], mask | (1 << (idx - 1)));
}

void explore_right(int idx, int diff, int mask) {
    if (idx > n) {
        if (diffLeft.count(-diff)) {
            for (int m : diffLeft[-diff]) {
                seen[mask | m] = true;
            }
        }
        return;
    }
    explore_right(idx + 1, diff, mask);
    explore_right(idx + 1, diff + arr[idx], mask | (1 << (idx - 1)));
    explore_right(idx + 1, diff - arr[idx], mask | (1 << (idx - 1)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    explore_left(1, 0, 0);
    explore_right(n / 2 + 1, 0, 0);
    int result = 0;
    for (int i = 1; i < (1 << n); i++) 
        if (seen[i]) result++;
    cout << result << endl;
    return 0;
}

This suffers from high constant factors due to map lookups and redundant checks.

Optimizaton with explicit separation and early marking:

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

int n, arr[55];
map<int, vector<int>> diffMap;
bool marked[1 << 20];
int ans = 0;

void gen_first_half(int idx, int diff, int st) {
    if (idx == n / 2 + 1) {
        diffMap[diff].push_back(st);
        return;
    }
    gen_first_half(idx + 1, diff, st);
    gen_first_half(idx + 1, diff + arr[idx], st | (1 << (idx - 1)));
    gen_first_half(idx + 1, diff - arr[idx], st | (1 << (idx - 1)));
}

void gen_second_half(int idx, int diff, int st) {
    if (idx == n + 1) {
        if (!diffMap.count(diff)) return;
        for (int m : diffMap[diff]) {
            int full = st | m;
            if (!marked[full]) {
                ans++;
                marked[full] = true;
            }
        }
        return;
    }
    gen_second_half(idx + 1, diff, st);
    gen_second_half(idx + 1, diff + arr[idx], st | (1 << (idx - 1)));
    gen_second_half(idx + 1, diff - arr[idx], st | (1 << (idx - 1)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    gen_first_half(1, 0, 0);
    gen_second_half(n / 2 + 1, 0, 0);
    cout << ans << endl;
    return 0;
}

Still borderline for large N due to memory and map overhead.

Final speedup using bitset compression:

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

int n, arr[55];
map<int, bitset<1 << 11>> diffBits;
bitset<1 << 11> visited[1 << 20];

void dfs_left(int idx, int diff, int st) {
    if (idx == n / 2 + 1) {
        diffBits[diff].set(st);
        return;
    }
    dfs_left(idx + 1, diff, st);
    dfs_left(idx + 1, diff + arr[idx], st | (1 << (idx - 1)));
    dfs_left(idx + 1, diff - arr[idx], st | (1 << (idx - 1)));
}

void dfs_right(int idx, int diff, int st) {
    if (idx == n + 1) {
        if (diffBits.count(diff)) {
            bitset<1 << 11> res = diffBits[diff] & (~visited[st]);
            ans += res.count();
            visited[st] |= res;
        }
        return;
    }
    dfs_right(idx + 1, diff, st);
    dfs_right(idx + 1, diff + arr[idx], st | (1 << (idx - 1)));
    dfs_right(idx + 1, diff - arr[idx], st | (1 << (idx - 1)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    dfs_left(1, 0, 0);
    dfs_right(n / 2 + 1, 0, 0);
    cout << ans << endl;
    return 0;
}

Here, bitset stores subset masks compactly and enables bulk operations, reducing both time and memory usage by avoiding per-element insertion into large vectors.