Knapsack

1. 1.0/1 Knapsack
   1D DP right-to-left loop: dp[w] = max(dp[w], val + dp[w-wt])medium
2. 2.Partition Equal Subset Sum
   Subset sum target = sum/2; 0/1 right-to-left boolean DPmedium
3. 3.Target Sum
   Transform P = (sum + target)/2; count 0/1 subsets with sum Pmedium
4. 4.Subset Sum
   Base 0/1 boolean DP: dp[s] = dp[s] || dp[s - num]medium
5. 5.Last Stone Weight II
   Min subset sum difference: find max subset sum S1 <= total/2medium
6. 6.Ones and Zeroes
   2D Capacity 0/1 DP: dp[z][o] updated backwards for each stringmedium
7. 7.Profitable Schemes
   Multi-dimensional 0/1 DP: members limit + min profit targethard
8. 8.Coin Change
   Unbounded 1D min coins DP: dp[a] = min(dp[a], 1 + dp[a-coin])medium
9. 9.Coin Change II
   Unbounded combination count: outer coin loop, inner amount left-to-rightmedium
10. 10.Combination Sum IV
    Unbounded permutation count: outer amount loop, inner coin loopmedium
11. 11.Perfect Squares
    Unbounded min items DP: dp[i] = min(dp[i], 1 + dp[i - s*s])medium
12. 12.Unbounded Knapsack
    1D DP left-to-right loop: dp[w] = max(dp[w], val + dp[w-wt])medium
13. 13.Rod Cutting
    Unbounded max value DP with piece lengths as item weightsmedium
14. 14.Minimum Cost to Fill Given Weight
    Unbounded min cost DP with exact weight capacity targetmedium
15. 15.Count Subsets With Given Sum
    0/1 counting DP: dp[s] = dp[s] + dp[s - num]medium
16. 16.Minimum Subset Sum Difference
    Subset sum reachability up to total/2; min diff = total - 2*S1medium
17. 17.Number of Subsets With Given Difference
    Subset sum count for target S1 = (total + diff)/2medium
18. 18.Integer Break
    Unbounded product maximization DP for integer split partsmedium
19. 19.Shopping Offers — related multidimensional state
    Multidimensional offer vector Knapsack / Memoized DFSmedium
20. 20.Tallest Billboard
    State difference DP: dp[diff] tracking max lower billboard heighthard

1. 21.Multiple Knapsack
   Item quantities limit DP with binary item decompositionhard
2. 22.Bounded Knapsack
   Binary splitting into 0/1 items (counts 1, 2, 4...) for O(N log K * W)medium
3. 23.Group Knapsack
   Choose at most 1 item per group: outer group loop, inner capacity right-to-leftmedium
4. 24.Multi-Dimensional Knapsack
   Multiple capacity limits (e.g. weight + volume) 2D/3D DP tableshard
5. 25.Knapsack with Value-Based DP
   Swap state: dp[val] = min weight required when total weight W is hugehard
6. 26.Meet-in-the-Middle Subset Sum — advanced
   Split N into N/2 parts + binary search when N <= 40 and W is hugehard
7. 27.Bitset Optimization for Subset Sum
   Bitwise shift subset sum: dp |= (dp << num) for 64x speeduphard
8. 28.Knapsack Reconstruction — return chosen items
   Backtrack table: compare dp[i][w] == dp[i-1][w] to identify chosen itemsmedium

1. Items + limited capacity limit?Knapsack DP
2. Every item can be used once?0/1 Knapsack (Right-to-Left loop)
3. Item can be reused unlimited times?Unbounded Knapsack (Left-to-Right loop)
4. Need only true/false reachability?Subset Sum DP
5. Need count of ways / combinations?Counting Knapsack DP

package main

import "fmt"

// 0/1 Knapsack: Items used ONCE -> Right-to-Left Capacity Loop
func knapsack01(weights []int, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    for i := 0; i < len(weights); i++ {
        wt, val := weights[i], values[i]
        // Loop Backwards to prevent reusing current item i
        for w := capacity; w >= wt; w-- {
            if val+dp[w-wt] > dp[w] {
                dp[w] = val + dp[w-wt]
            }
        }
    }
    return dp[capacity]
}

// Unbounded Knapsack: Items REUSED -> Left-to-Right Capacity Loop
func unboundedKnapsack(weights []int, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    for i := 0; i < len(weights); i++ {
        wt, val := weights[i], values[i]
        // Loop Forwards to allow reusing current item i multiple times
        for w := wt; w <= capacity; w++ {
            if val+dp[w-wt] > dp[w] {
                dp[w] = val + dp[w-wt]
            }
        }
    }
    return dp[capacity]
}

func main() {
    weights := []int{2, 3, 4}
    values := []int{6, 10, 12}
    cap := 5

    fmt.Println("0/1 Max Value:", knapsack01(weights, values, cap))             // Output: 16 (Items 2+3)
    fmt.Println("Unbounded Max Value:", unboundedKnapsack(weights, values, cap)) // Output: 16
}

Core Knapsack Mechanics & Loop Directions

Define dp[i][w] State Meaning → Compare Take vs Skip Choice
0/1 Knapsack -> Capacity Loop Right-to-Left (Backwards)
Unbounded Knapsack -> Capacity Loop Left-to-Right (Forwards)
Combinations Count -> for coin in coins { for amount in coin..W }
Permutations Count -> for amount in 1..W { for coin in coins }
Pseudo-Polynomial Time -> O(N * Capacity); W = 10^9 requires value-based DP or meet-in-middle

Knapsack Variants & Loop Ordering

Common Interview Mistakes

• • Failing to identify 0/1 vs Unbounded item reuse rules before choosing capacity loop directions.
• • Running 0/1 Knapsack 1D capacity loop forwards (accidentally allowing item reuse).
• • Using 0 base initialization for counting/boolean problems instead of dp[0] = 1 or dp[0] = true.
• • Swapping loop order in Coin Change II (accidentally counting permutations instead of combinations).
• • Updating DP values when item weight > current capacity w (item does not fit).
• • Assuming Knapsack complexity is always polynomial (it is pseudo-polynomial in capacity W).
• • Attempting full capacity 1D DP when W = 10^9 (causes memory overflow; requires value-based DP or meet-in-middle).
• • Confusing subset selection (unordered item choices) with subsequence ordering.
• • Failing to check odd total sum in Partition Equal Subset Sum (odd sum can never be halved into integers).

Interview Rules

Item choices + capacity limit? → Knapsack DP
Rule 1                         → Define dp[i][w] state meaning explicitly
Rule 2                         → 0/1 (Use once) = 1D Capacity Loop Right-to-Left
Rule 3                         → Unbounded (Reuse) = 1D Capacity Loop Left-to-Right
Rule 4                         → Subset Sum = Boolean reachability dp[0] = true
Rule 5                         → Combinations count = Outer coin loop; Permutations count = Outer amount loop
Rule 6                         → Massive capacity W = 10^9? Use Value-based DP or Meet-in-middle
Time Complexity                → O(N * Capacity) (Pseudo-Polynomial)
Space Complexity               → O(N * Capacity) 2D Table or O(Capacity) 1D Array

💡 Golden Rule: For each item, compare taking it against skipping it, while keeping enough capacity state to prevent using more resources than allowed.

Knapsack Core: TAKE vs SKIP decision
0/1 (Use Once): Capacity Loop Right-to-Left (w = W down to wt)
Unbounded (Reuse): Capacity Loop Left-to-Right (w = wt up to W)
Subset Sum Target: P = (total + target) / 2
Combinations: for coin { for amount }
Permutations: for amount { for coin }
Pseudo-Polynomial: Time = O(N * W), Space = O(W)