Subset Sum and Partition DP: Backtracking vs DP

def subset_sum_all(nums, target):
    result = []
    nums.sort()
    def bt(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining: break  # pruning
            current.append(nums[i])
            bt(i + 1, current, remaining - nums[i])
            current.pop()
    bt(0, [], target)
    return result

# DP (existence only)
def subset_sum_exists(nums, target):
    dp = {0}
    for n in nums:
        dp |= {x + n for x in dp}
    return target in dp

# DP (count ways)
def subset_sum_count(nums, target, mod=10**9+7):
    dp = [0] * (target + 1)
    dp[0] = 1
    for n in nums:
        for t in range(target, n-1, -1):  # reverse to avoid reuse
            dp[t] = (dp[t] + dp[t-n]) % mod
    return dp[target]

# DP (min elements to reach target)
def subset_sum_min(nums, target):
    dp = [float('inf')] * (target + 1)
    dp[0] = 0
    for n in nums:
        for t in range(n, target + 1):  # forward: reuse allowed
            dp[t] = min(dp[t], dp[t-n] + 1)
    return dp[target] if dp[target] != float('inf') else -1

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

// O(n * target / 64) with bitset
bool subsetSumBitset(vector<int>& nums, int target) {
    bitset<100001> dp;
    dp[0] = 1;
    for (int n : nums) dp |= dp << n;
    return dp[target];
}

public class SubsetSum {
    // Count subsets with given sum
    public int countSubsets(int[] nums, int target) {
        int MOD = 1_000_000_007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int n : nums)
            for (int t = target; t >= n; t--)
                dp[t] = (dp[t] + dp[t - n]) % MOD;
        return dp[target];
    }
}