Knapsack DP

┌─────────────────────────────────────────────────────────────────────────┐
│                     DP KNAPSACK PATTERN MATRIX                          │
└─────────────────────────────────────────────────────────────────────────┘

                          COUNT WAYS              FIND MIN/MAX
                    ┌──────────────────┬──────────────────────────┐
                    │                  │                          │
ORDER MATTERS?      │  PERMUTATIONS    │   Not typically used     │
(Yes)              │  LC 377          │   (Use Permutations      │
                    │  Target→Item     │    for counting)         │
                    │  Forward         │                          │
                    ├──────────────────┼──────────────────────────┤
                    │                  │                          │
ORDER DOESN'T       │  COMBINATIONS    │   UNBOUNDED KNAPSACK     │
MATTER              │  LC 518          │   LC 322                 │
(No)                │  Item→Target     │   Item→Capacity          │
                    │  Forward         │   Forward                │
                    ├──────────────────┼──────────────────────────┤
                    │                  │                          │
USE EACH ONCE       │  Not typical     │   0/1 KNAPSACK           │
(Constraint)        │  (Can adapt      │   LC 416                 │
                    │   0/1 pattern)   │   Item→Capacity          │
                    │                  │   BACKWARD ⚠️            │
                    └──────────────────┴──────────────────────────┘

Legend:
  Item→Target     = Outer loop: items,    Inner loop: target
  Target→Item     = Outer loop: target,   Inner loop: items
  Forward         = Inner loop: i to target (allows reuse)
  BACKWARD ⚠️     = Inner loop: target to i (prevents reuse)

Start
  │
  ├─ Question asks "count ways"?
  │   │
  │   ├─ YES → Order matters?
  │   │         ├─ YES → Permutations (Target→Item) [LC 377]
  │   │         └─ NO  → Combinations (Item→Target) [LC 518]
  │   │
  │   └─ NO  → Question asks "min/max"?
  │             │
  │             ├─ Each item once?
  │             │   ├─ YES → 0/1 Knapsack (BACKWARD) [LC 416]
  │             │   └─ NO  → Unbounded (FORWARD) [LC 322]
  │             │
  │             └─ Unknown → Check problem constraints

// java
// IDEA: the four knapsack loop orders side by side — each differs only in nesting/direction
// time = O(n * W), space = O(W)
// ============================================
// PATTERN 1: COMBINATIONS (Item → Target)
// ============================================
// LC 518: Coin Change II
public int countCombinations(int target, int[] items) {
    int[] dp = new int[target + 1];
    dp[0] = 1;  // Base: one way to make 0

    // OUTER: Items/Coins
    for (int item : items) {
        // INNER: Target/Amount (forward)
        for (int i = item; i <= target; i++) {
            dp[i] += dp[i - item];  // ← Same transition
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 2: PERMUTATIONS (Target → Item)
// ============================================
// LC 377: Combination Sum IV
public int countPermutations(int target, int[] items) {
    int[] dp = new int[target + 1];
    dp[0] = 1;  // Base: one way to make 0

    // OUTER: Target/Amount
    for (int i = 1; i <= target; i++) {
        // INNER: Items/Coins
        for (int item : items) {
            if (i >= item) {
                dp[i] += dp[i - item];  // ← Same transition
            }
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 3: 0/1 KNAPSACK (Item → Capacity BACKWARDS)
// ============================================
// LC 416: Partition Equal Subset Sum
public boolean canPartition(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // Base: can make 0

    // OUTER: Items
    for (int num : nums) {
        // INNER: Capacity (BACKWARDS to prevent reuse)
        for (int w = target; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];  // ← Different transition (OR)
        }
    }
    return dp[target];
}

// ============================================
// PATTERN 4: UNBOUNDED KNAPSACK (Item → Capacity FORWARDS)
// ============================================
// LC 322: Coin Change (minimum coins)
public int minCoins(int target, int[] coins) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, target + 1);  // Infinity
    dp[0] = 0;  // Base: 0 coins for 0 amount

    // OUTER: Items/Coins
    for (int coin : coins) {
        // INNER: Target (FORWARDS allows reuse)
        for (int i = coin; i <= target; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);  // ← Different transition (MIN)
        }
    }
    return dp[target] > target ? -1 : dp[target];
}

Question: What does the problem ask for?

├─ "Count number of ways/combinations to reach target"
│  ├─ Order matters? (e.g., [1,2] ≠ [2,1])
│  │  ├─ YES → Use PERMUTATIONS pattern (Target → Item)
│  │  │         Example: LC 377 Combination Sum IV
│  │  └─ NO  → Use COMBINATIONS pattern (Item → Target)
│  │            Example: LC 518 Coin Change II
│  │
│  └─ Can reuse items?
│     ├─ YES → Unbounded, iterate forwards
│     └─ NO  → 0/1 Knapsack, iterate backwards
│
└─ "Find minimum/maximum value"
   ├─ Can reuse items?
   │  ├─ YES → Unbounded Knapsack (forwards)
   │  │         Example: LC 322 Coin Change (min coins)
   │  └─ NO  → 0/1 Knapsack (backwards)
   │            Example: LC 416 Partition Equal Subset Sum
   │
   └─ Always use (Item → Capacity) order

Given: stones = [2, 7, 4, 1, 8, 1]
Total sum = 23

Goal: Split into two groups with min |sum1 - sum2|

Mathematical insight:
  Let sum1 = S (sum of group 1)
  Then sum2 = total - S (sum of group 2)
  
  Difference = |sum1 - sum2| = |S - (total - S)| = |2S - total|
  
  To minimize this: Maximize S such that S ≤ total/2
  
  Result = total - 2*S (where S is the largest achievable sum ≤ total/2)

// java
// LC 1049 - Last Stone Weight II
// IDEA: variant 1 — boolean subset sum; can we reach exactly `sum`?
// time = O(n * total), space = O(total)
public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int stone : stones) {
        total += stone;
    }

    int target = total / 2;
    
    // dp[j] = can we achieve sum j?
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // Base: always can make sum 0 (choose nothing)

    // For each stone
    for (int stone : stones) {
        // Iterate BACKWARDS to prevent using same stone twice
        for (int j = target; j >= stone; j--) {
            dp[j] = dp[j] || dp[j - stone];  // Can achieve j if:
                                              // (already could) OR (could make j-stone and add this stone)
        }
    }

    // Find largest achievable sum ≤ target
    for (int j = target; j >= 0; j--) {
        if (dp[j]) {
            return total - 2 * j;
        }
    }

    return 0;
}

// java
// LC 1049 - Last Stone Weight II
// IDEA: variant 2 — maximise the achievable subset sum <= total/2, answer = total - 2*best
// time = O(n * total), space = O(total)
public int lastStoneWeightII(int[] stones) {
    int total = 0;
    for (int stone : stones) {
        total += stone;
    }

    int target = total / 2;
    
    // dp[j] = maximum sum we can achieve ≤ j
    int[] dp = new int[target + 1];
    dp[0] = 0;  // Base: can make sum 0

    // For each stone
    for (int stone : stones) {
        // Iterate BACKWARDS to prevent reuse
        for (int j = target; j >= stone; j--) {
            // Either skip this stone (dp[j])
            // Or include it and add to best we could do with j-stone (dp[j-stone] + stone)
            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
    }

    return total - 2 * dp[target];
}

❌ WRONG: Forward iteration (causes reuse)
for (int j = stone; j <= target; j++) {
    dp[j] = dp[j] || dp[j - stone];
}
Problem: When we update dp[j], we're using the NEW value of dp[j-stone]
         which might have already been updated by the same stone in this iteration.
         This allows using the same stone multiple times!

Example with stone=3, target=9:
  j=3: dp[3] = dp[0] = true ✓
  j=6: dp[6] = dp[3] = true ✓ BUT dp[3] was just updated by the same stone!
  j=9: dp[9] = dp[6] = true ✓ Again, using same stone multiple times!

✅ CORRECT: Backward iteration (prevents reuse)
for (int j = target; j >= stone; j--) {
    dp[j] = dp[j] || dp[j - stone];
}
Reason: We process from right to left, so dp[j-stone] is always from the PREVIOUS iteration
        (before this stone was considered). So we use each stone only once.

Example with stone=3, target=9:
  j=9: dp[9] = dp[6] (old value from previous stone) ✓
  j=6: dp[6] = dp[3] (old value from previous stone) ✓
  j=3: dp[3] = dp[0] (old value from previous stone) ✓

stones = [2, 7, 4, 1, 8, 1]
total = 23
target = 23 / 2 = 11

Initial: dp = [T, F, F, F, F, F, F, F, F, F, F, F]

After stone 2:
  dp[2] = T (can make sum 2)
  dp = [T, F, T, F, F, F, F, F, F, F, F, F]

After stone 7:
  dp[9] = T (can make 2+7)
  dp[7] = T
  dp[2] = T (unchanged)
  dp = [T, F, T, F, F, F, F, T, F, T, F, F]

After stone 4:
  dp[11] = T (can make 7+4)
  dp[9] = T (unchanged)
  dp[6] = T (can make 2+4)
  dp[4] = T
  dp = [T, F, T, F, T, F, T, T, F, T, F, T]

... continue for remaining stones ...

Final: Find largest j ≤ 11 where dp[j] = T
       Result = 23 - 2 * j

Question: Can we partition into two equal subsets?
Answer: Can we achieve sum = total/2?
DP: boolean[] dp where dp[j] = can we make sum j?
Return: dp[total/2]

Question: Assign +/- to reach target T
Transformation: Let sum1 = sum of items with +
                Let sum2 = sum of items with -
                sum1 - sum2 = T
                sum1 + sum2 = total (all items)
                
                Solving: sum1 = (total + T) / 2

Feasibility first (both are required before the DP runs):
    abs(T) > total          -> 0 ways: even all-plus or all-minus cannot reach T
    (total + T) is odd      -> 0 ways: sum1 would not be an integer

So: This is 0/1 knapsack! Find count of subsets with sum = (total + T) / 2
DP: int[] dp where dp[j] = count of ways to make sum j
Return: dp[(total + T) / 2]

// java
// LC 494 - Target Sum
// IDEA: reduce "assign +/-" to "count subsets summing to (total + T) / 2", then 0/1 knapsack
// time = O(n * target), space = O(target)
public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;

    // NOTE !!! guard before the division — otherwise `sub` is negative or non-integral
    if (Math.abs(target) > total || ((total + target) % 2) != 0) return 0;

    int sub = (total + target) / 2;
    int[] dp = new int[sub + 1];
    dp[0] = 1;                                  // one way to make 0: pick nothing
    for (int num : nums) {
        for (int j = sub; j >= num; j--) {      // backward -> each num used at most once
            dp[j] += dp[j - num];
        }
    }
    return dp[sub];
}

// java
// IDEA: coins outer, amount inner -> each coin is offered once, so sets are counted
// time = O(n * amount), space = O(amount)
// LC 518: Coin Change II - Count combinations
// Example: [1,2] and [2,1] are the SAME combination
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // Base case: 1 way to make amount 0

    // OUTER LOOP: Iterate through each coin
    // This ensures we process all uses of one coin before moving to the next,
    // which prevents duplicate combinations like [1,2] and [2,1].
    for (int coin : coins) {
        // INNER LOOP: Update dp table for all amounts reachable by this coin
        for (int i = coin; i <= amount; i++) {
            // Number of ways to make amount 'i' is:
            // (Current ways) + (Ways to make 'i - coin')
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

After coin 1: dp = [1, 1, 1, 1]  // {}, {1}, {1,1}, {1,1,1}
After coin 2: dp = [1, 1, 2, 2]  // + {2}, {1,2}
Result: 2 combinations → {1,1,1}, {1,2}

// java
// IDEA: amount outer, coins inner -> every coin is retried at every amount, so orderings count
// time = O(n * target), space = O(target)
// LC 377: Combination Sum IV - Count permutations
// Example: [1,2] and [2,1] are DIFFERENT permutations
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;

    // OUTER LOOP: Iterate through each amount
    // For each amount, try all coins to see which was "last added"
    for (int i = 1; i <= target; i++) {
        // INNER LOOP: Try each coin for current amount
        for (int num : nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];
}

dp[1]: Use 1 → [1] (1 way)
dp[2]: Use 1 → [1,1], Use 2 → [2] (2 ways)
dp[3]: From dp[2] add 1 → [1,1,1], [2,1]
       From dp[1] add 2 → [1,2]
Result: 3 permutations → {1,1,1}, {1,2}, {2,1}

// java
// LC 518 - Coin Change II
// IDEA: combinations — coins outer
// time = O(n * amount), space = O(amount)
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // Base: 1 way to make 0

    // CRITICAL: Coin outer loop = COMBINATIONS
    for (int coin : coins) {              // ← Process coins one by one
        for (int i = coin; i <= amount; i++) {  // ← Update all amounts for this coin
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

// Example: amount=3, coins=[1,2]
// Result: 2 combinations
// {1,1,1}, {1,2}  (Note: [1,2] and [2,1] counted as same)

// java
// LC 377 - Combination Sum IV
// IDEA: permutations — amount outer
// time = O(n * target), space = O(target)
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1; // Base: 1 way to make 0

    // CRITICAL: Amount outer loop = PERMUTATIONS
    for (int i = 1; i <= target; i++) {   // ← Process each amount
        for (int num : nums) {            // ← Try every number for this amount
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

// Example: target=3, nums=[1,2]
// Result: 3 permutations
// {1,1,1}, {1,2}, {2,1}  (Note: [1,2] and [2,1] are different)

Initialize: dp = [1, 0, 0, 0]

Process coin 1:
  i=1: dp[1] += dp[0] = 1    → [1, 1, 0, 0]  // ways: {1}
  i=2: dp[2] += dp[1] = 1    → [1, 1, 1, 0]  // ways: {1,1}
  i=3: dp[3] += dp[2] = 1    → [1, 1, 1, 1]  // ways: {1,1,1}

Process coin 2:
  i=2: dp[2] += dp[0] = 1+1=2 → [1, 1, 2, 1]  // ways: {1,1}, {2}
  i=3: dp[3] += dp[1] = 1+1=2 → [1, 1, 2, 2]  // ways: {1,1,1}, {1,2}
                                              // Note: Can't get {2,1} because
                                              // all coin-1 uses are done before coin-2

Final: dp[3] = 2  ✅ Only {1,1,1} and {1,2}

Initialize: dp = [1, 0, 0, 0]

i=1 (building sum 1):
  Try 1: dp[1] += dp[0] = 1   → [1, 1, 0, 0]  // ways: {1}
  Try 2: skip (2 > 1)

i=2 (building sum 2):
  Try 1: dp[2] += dp[1] = 1   → [1, 1, 1, 0]  // {1} + 1 = {1,1}
  Try 2: dp[2] += dp[0] = 1+1=2 → [1, 1, 2, 0]  // {} + 2 = {2}

i=3 (building sum 3):
  Try 1: dp[3] += dp[2] = 2   → [1, 1, 2, 2]  // {1,1} + 1 = {1,1,1}
                                              // {2} + 1 = {2,1}  ✅
  Try 2: dp[3] += dp[1] = 2+1=3 → [1, 1, 2, 3]  // {1} + 2 = {1,2}  ✅

Final: dp[3] = 3  ✅ All three: {1,1,1}, {1,2}, {2,1}

// java
// LC 518 - Coin Change II
// IDEA: count the ways to form each amount; coins outer keeps `{1,2}` and `{2,1}` as one
// time = O(n * amount), space = O(amount)
public int change(int amount, int[] coins) {
    // dp[i] = total number of combinations that make up amount i
    int[] dp = new int[amount + 1];

    // Base case: There is exactly 1 way to make 0 amount (empty set)
    dp[0] = 1;

    // CRITICAL: Coin outer loop = COMBINATIONS
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

Input: amount = 5, coins = [1,2,5]
Output: 4
Combinations: {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}

Input: amount = 3, coins = [2]
Output: 0
Explanation: Cannot make 3 with only coins of 2

// java
// IDEA: the two nestings printed together — the only difference is which loop is outer
// time = O(n * amount), space = O(amount)
// LC 518: Combinations
for (int coin : coins)              // ← ITEM OUTER
    for (int i = coin; i <= amount; i++)

// LC 377: Permutations
for (int i = 1; i <= target; i++)   // ← TARGET OUTER
    for (int num : nums)

// java
// LC 322 - Coin Change
// IDEA: min coins per amount; order is irrelevant so either nesting works
// time = O(n * amount), space = O(amount)
public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;

    // dp[i] = min coins to make amount i
    int[] dp = new int[amount + 1];

    // Initialize with "Infinity" (amount + 1 is safe)
    Arrays.fill(dp, amount + 1);

    // Base case: 0 coins needed for 0 amount
    dp[0] = 0;

    // Iterate through every amount from 1 to amount
    for (int i = 1; i <= amount; i++) {
        // For each amount, try every coin
        for (int coin : coins) {
            // CRITICAL CONDITION: Check if coin fits
            if (i >= coin) {
                // DP equation: Min of (current value) OR
                // (1 coin + coins needed for remainder)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // If value is still "Infinity", we couldn't reach it
    return dp[amount] > amount ? -1 : dp[amount];
}

dp[capacity] = best value     ->   "how much have I packed?"
dp[difference] = best height  ->   "how unbalanced are the two piles?"

dp[d] = the tallest achievable TALLER side, over all ways to split some subset
        of the rods so far into two piles differing by exactly d

dp[0] = 0   (two empty piles, difference 0, height 0)
answer = dp[0] after all rods -- difference 0 means equal, and we kept the max height

skip it            ->  (d,        taller)                 unchanged
put on TALLER      ->  (d + x,    taller + x)             the gap widens
put on SHORTER     ->  (|d - x|,  max(taller, shorter+x)) the gap closes, and may flip sides
                       where shorter = taller - d

// java
// LC 956 - Tallest Billboard
// IDEA: key the table by the DIFFERENCE between the two supports, store the taller
//       support's height. Answer = dp[0], the best height at difference zero.
// time = O(n * sum), space = O(sum)
public int tallestBillboard(int[] rods) {
    int sum = 0;
    for (int r : rods) sum += r;

    int[] dp = new int[sum + 1];
    Arrays.fill(dp, -1);          // NOTE !!! -1 = unreachable; 0 is a real, reachable height
    dp[0] = 0;

    for (int x : rods) {
        int[] prev = dp.clone();  // "skip x" is prev carried forward, already in dp
        for (int d = 0; d <= sum; d++) {
            if (prev[d] < 0) continue;
            int taller = prev[d], shorter = taller - d;

            // 1) x joins the taller pile -> gap widens by x
            if (d + x <= sum) dp[d + x] = Math.max(dp[d + x], taller + x);

            // 2) x joins the shorter pile -> gap becomes |d - x|, piles may swap
            int nd = Math.abs(d - x);
            dp[nd] = Math.max(dp[nd], Math.max(taller, shorter + x));
        }
    }
    return dp[0];
}

# python
# LC 956 - Tallest Billboard
# IDEA: dict from difference -> tallest "taller side"; only reachable differences are stored
# time = O(n * sum), space = O(sum)
def tallestBillboard(rods):
    dp = {0: 0}                        # difference -> height of the taller support

    for x in rods:
        prev = dict(dp)                # snapshot: each rod is used at most once
        for d, taller in prev.items():
            shorter = taller - d

            nd, nt = d + x, taller + x                 # x on the taller side
            dp[nd] = max(dp.get(nd, 0), nt)

            nd2 = abs(d - x)                           # x on the shorter side
            dp[nd2] = max(dp.get(nd2, 0), max(taller, shorter + x))

    return dp[0]

start        {0: 0}
after 1      {0: 0, 1: 1}
after 2      {0: 0, 1: 2, 2: 2, 3: 3}
after 3      {0: 3, 1: 3, 2: 4, 3: 3, 4: 5, 5: 5, 6: 6}
after 6      {0: 6, 1: 6, 2: 7, 3: 6, ...}   -> dp[0] = 6, supports {6} and {1,2,3}

0/1     item i  ->  (w, v)                       take it or don't
group   item i  ->  {(w, c), (w', c'), ...}      take AT MOST ONE of these

0/1     dp[s] = best( dp[s],  dp[s - w] + v )                 ONE candidate
group   dp[s] = best( dp[s],  best over the item's options )  |group| candidates

dp[s] = fewest operations to make SOME subset of the elements seen so far sum to exactly s
dp[0] = 0, everything else INF
answer = dp[sum], or -1 if it never left INF

✅ snapshot         read prev, write into a copy   every option competes against the state BEFORE the item
✅ capacity OUTER   for s in W..0:                  dp[s-w] is a smaller index, not yet touched by this item
                        for (w, c) in group:
❌ options OUTER    for (w, c) in group:            option B reads a dp[] that option A has already updated
                        for s in W..w:

# python
# The group knapsack skeleton -- both correct orders, minimisation flavour
# time = O(n * W * |group|), space = O(W)
def group_knapsack(groups, W):
    INF = float('inf')
    dp = [INF] * (W + 1)
    dp[0] = 0

    for options in groups:                       # options = [(weight, cost), ...]

        # form A -- snapshot: dp is read-only for the whole group
        new_dp = dp[:]
        for w, c in options:
            for s in range(w, W + 1):
                if dp[s - w] != INF:
                    new_dp[s] = min(new_dp[s], dp[s - w] + c)
        dp = new_dp

        # form B -- in place, capacity OUTER and backward (no copy needed)
        # for s in range(W, -1, -1):
        #     for w, c in options:
        #         if s >= w and dp[s - w] != INF:
        #             dp[s] = min(dp[s], dp[s - w] + c)

    return dp[W]

x, 2x, 4x, ...        k doublings, cost k
x, x//2, x//4, ...    k halvings,  cost k

x = 10, sum = 13  ->  (10, 0), (5, 1), (2, 2), (1, 3)      20 is already over sum
x =  2, sum = 13  ->  (2, 0), (4, 1), (8, 2), (1, 1)

# python
# LC 4040 - Minimum Operations to Form Subset Sum I
# IDEA: group 0/1 knapsack -- each x is a menu of (value, ops); take at most one entry per x
# time = O(n * sum * log(max(x, sum))), space = O(sum)
def minOperations(nums, sum):
    INF = float('inf')
    dp = [INF] * (sum + 1)                 # dp[s] = min ops for a subset summing to s
    dp[0] = 0

    for x in nums:
        options = []
        if x <= sum:
            options.append((x, 0))         # NOTE !!! keep x untouched -- the zero-cost option
        value, op = x, 0
        while value <= sum:                # x, 2x, 4x, ...
            if op > 0:
                options.append((value, op))
            value *= 2
            op += 1
        value, op = x, 0
        while value > 0:                   # x//2, x//4, ...
            value, op = value // 2, op + 1
            if value == 0:
                break
            if value <= sum:
                options.append((value, op))

        new_dp = dp[:]                     # NOTE !!! snapshot => x is used at most once,
        for value, cost in options:        #          in at most one of its forms
            for s in range(value, sum + 1):
                if dp[s - value] != INF:
                    new_dp[s] = min(new_dp[s], dp[s - value] + cost)
        dp = new_dp

    return -1 if dp[sum] == INF else dp[sum]

// java
// LC 4040 - Minimum Operations to Form Subset Sum I
// IDEA: same group knapsack, written in place with the capacity loop OUTER and backward
// time = O(n * sum * log(max(x, sum))), space = O(sum)
public int minOperations(int[] nums, int sum) {
    final int INF = Integer.MAX_VALUE / 2;
    int[] dp = new int[sum + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;

    for (int x : nums) {
        List<int[]> options = new ArrayList<>();
        for (long v = x, op = 0; v <= sum; v *= 2, op++)      // x, 2x, 4x, ...  (op = 0 keeps x)
            options.add(new int[]{(int) v, (int) op});
        for (long v = x, op = 0; v > 0; ) {                   // x/2, x/4, ...
            v /= 2;
            op++;
            if (v == 0) break;
            if (v <= sum) options.add(new int[]{(int) v, (int) op});
        }

        for (int s = sum; s >= 0; s--) {                      // NOTE !!! capacity OUTER, backward
            for (int[] o : options) {                         //          options INNER
                int value = o[0], cost = o[1];
                if (s >= value && dp[s - value] != INF)
                    dp[s] = Math.min(dp[s], dp[s - value] + cost);
            }
        }
    }
    return dp[sum] >= INF ? -1 : dp[sum];
}

groups       10 -> (10,0) (5,1) (2,2) (1,3)
              2 -> (2,0)  (4,1) (8,2) (1,1)

start        {0:0}
after 10     {0:0, 1:3, 2:2, 5:1, 10:0}
after 2      {0:0, 1:1, 2:0, 3:3, 4:1, 5:1, 6:2, 7:1, 8:2, 9:2, 10:0, 11:1, 12:0, 13:3}
                                                                                  ^
                                              dp[13] = dp[5] + 2 = 1 + 2 -> 10->5 and 2->4->8

Does one item offer SEVERAL mutually exclusive options?
│
├─ YES ──► Group Knapsack  [4040, 1155, 2218, 2585]
│          for group in groups:
│              for w in range(W, -1, -1):             # CAPACITY outer, backward
│                  for (weight, cost) in group:       # options inner
│          └─ or snapshot dp and let every option read the pre-group state
│          └─ options-outer + in-place dp is the classic bug: two forms of one item
│
└─ NO  ──► Is each item reusable?
    │
    ├─ NO  ──► 0/1 Knapsack
    │          for item in items:
    │              for w in range(W, weight-1, -1):     # BACKWARD
    │          └─ asks "can we hit the sum?"  -> boolean dp
    │          └─ asks "how many ways?"       -> dp[j] += dp[j-w]
    │          └─ asks "best value?"          -> dp[j] = max(dp[j], dp[j-w]+v)
    │
    └─ YES ──► Does order matter?
               │
               ├─ NO  (combinations, {1,2} == {2,1})  ──► items outer, amount inner  [518]
               ├─ YES (permutations, {1,2} != {2,1})  ──► amount outer, items inner  [377]
               └─ Min/max only (order irrelevant)     ──► either nesting             [322, 279]