Knapsack & Subset DP

The problem family

You have items, each with a weight (cost) and a value, and a capacity W. Choose items to maximize value without exceeding W. Variants change how many times each item can be used and what you're computing.

0/1 knapsack

State: dp[i][w] = best value using the first i items with capacity w. Transition: skip item i, or take it: dp[i][w] = max(dp[i−1][w], dp[i−1][w − wt] + val).

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)
    return dp[n][W]

The 1D version and why it goes backwards

def knapsack_01_1d(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):      # BACKWARDS
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

int knapsack01(vector<int>& wt, vector<int>& val, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)wt.size(); i++)
        for (int w = W; w >= wt[i]; w--)
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}

Subset sum and partition

Values don't matter, only reachability: dp[s] = can some subset sum to s?

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2) return false;
    bitset<10001> bits;               // bit s = sum s reachable (max sum/2 here is 10000)
    bits[0] = 1;
    for (int x : nums) bits |= bits << x;
    return bits[total / 2];
}

Target Sum → subset count

Assigning + or − to each number: if P is the plus-set, P − (total − P) = target → P = (total + target) / 2. Count subsets with that sum.

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    goal = (total + target) // 2
    dp = [0] * (goal + 1)
    dp[0] = 1
    for x in nums:
        for s in range(goal, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[goal]

Minimizing the difference between two groups

Last Stone Weight II: find the reachable subset sum closest to total // 2; the answer is total − 2·best.

Unbounded knapsack

Each item can be reused → iterate capacity forwards.

def coin_change_min(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):      # FORWARDS: reuse allowed
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Combinations vs permutations (loop order!)

Counting the ways to make amount with coins:

# Combinations: {1,2} and {2,1} are the SAME → coins outer
def change(amount, coins):
    dp = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

# Permutations / ordered sequences: 1+2 and 2+1 are DIFFERENT → amount outer
def combination_sum4(nums, target):
    dp = [1] + [0] * target
    for a in range(1, target + 1):
        for x in nums:
            if x <= a:
                dp[a] += dp[a - x]
    return dp[target]

// combinations
int change(int amount, vector<int>& coins) {
    vector<unsigned long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
    return dp[amount];
}

Multi-dimensional capacity

Ones and Zeroes: each string costs some zeros and some ones. Capacity becomes 2D; still 0/1, still backwards in both dimensions.

def find_max_form(strs, m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for s in strs:
        z, o = s.count("0"), s.count("1")
        for i in range(m, z - 1, -1):
            for j in range(n, o - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1)
    return dp[m][n]

Bounded knapsack (limited copies)

Item i has cᵢ copies. Split cᵢ into powers of two (1, 2, 4, …, remainder) — each chunk becomes a 0/1 item, and any count 0..cᵢ is a sum of chunks. O(W · Σ log cᵢ).

Group knapsack

Items come in groups and you pick exactly one (or at most one) per group — e.g. each die contributes one face (Number of Dice Rolls With Target Sum).

def num_rolls_to_target(n, k, target):
    MOD = 10**9 + 7
    dp = [1] + [0] * target
    for _ in range(n):                       # each die is a group
        new = [0] * (target + 1)
        for s in range(1, target + 1):
            for face in range(1, min(k, s) + 1):
                new[s] = (new[s] + dp[s - face]) % MOD
        dp = new
    return dp[target]

When W is too large: meet in the middle

If n ≤ 40 but values are huge, split the items into two halves, enumerate all 2^(n/2) subset sums of each, sort one side, and combine with binary search or two pointers. O(2^(n/2) · n).

Complexity

O(n · W) time, O(W) space with the 1D table. Note this is pseudo-polynomial: fast when W is small, hopeless when W is 10¹⁸.

Common mistakes

• Wrong loop direction (forwards for 0/1 or backwards for unbounded).
• Wrong loop nesting for combinations vs permutations.
• Forgetting parity/bounds checks in Target Sum (negative or odd goal).
• Using int for counts that overflow (use modulo or 64-bit).
• Initializing a minimization table with 0 instead of ∞.