0/1 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
   Target = total/2; 0/1 right-to-left boolean DPmedium
3. 3.Subset Sum
   0/1 reachability: dp[s] = dp[s] || dp[s - num] updated backwardsmedium
4. 4.Target Sum
   Transform P = (total + target)/2; count 0/1 subsets with sum Pmedium
5. 5.Last Stone Weight II
   Min subset sum diff: max subset sum S1 <= total/2; ans = total - 2*S1medium
6. 6.Minimum Subset Sum Difference
   0/1 subset reachability; find largest S1 <= total/2medium
7. 7.Count Subsets With Given Sum
   0/1 counting: dp[s] += dp[s - num] updated backwardsmedium
8. 8.Number of Subsets With Given Difference
   Count subsets for sum S1 = (total + diff)/2medium
9. 9.Ones and Zeroes
   2D Capacity 0/1 DP: dp[z][o] updated backwards for each stringmedium
10. 10.Tallest Billboard
    State difference 0/1 DP: dp[diff] tracking max lower heighthard
11. 11.Profitable Schemes
    Multi-dimensional 0/1 DP: members limit + min profit targethard
12. 12.Find Target Sum Ways
    Subset sum counting with zeroes explicit handlingmedium
13. 13.Equal Sum Partition
    Partition Equal Subset Sum boolean 0/1 mappingmedium
14. 14.Knapsack With Exact Capacity
    Initialize dp[0] = 0, other capacities to -INF to enforce exact fillmedium
15. 15.Return Selected Items in Knapsack
    Backtrack 2D matrix: compare dp[i][w] == dp[i-1][w] to identify chosen itemsmedium

1. 16.Multi-Dimensional 0/1 Knapsack
   Multiple capacity dimensions (e.g. weight + volume) updated backwardshard
2. 17.Value-Based Knapsack DP
   Swap state: dp[val] = min weight when total capacity W is hugehard
3. 18.Bitset Subset Sum Optimization
   Bitwise shift: dp |= (dp << num) for 64x subset sum accelerationhard
4. 19.Meet-in-the-Middle Subset Sum
   Split N into N/2 parts + binary search when N <= 40 and W is hugehard
5. 20.Group Knapsack — advanced
   Choose at most 1 item per group: outer group loop, inner capacity right-to-lefthard

1. Each item usable only once?0/1 Knapsack
2. Main decision for each item?TAKE (once) or SKIP
3. Limited capacity / target?dp[item][capacity]
4. Using 1D DP array?Capacity loop RIGHT -> LEFT
5. Need split array into 2 equal parts?Target = total / 2

package main

import "fmt"

// 0/1 Knapsack 2D Matrix DP: O(N * W) space
func knapsack2D(weights []int, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        wt, val := weights[i-1], values[i-1]
        for w := 0; w <= capacity; w++ {
            dp[i][w] = dp[i-1][w] // SKIP item i
            if wt <= w {
                take := val + dp[i-1][w-wt] // TAKE item i (reads previous row i-1)
                if take > dp[i][w] {
                    dp[i][w] = take
                }
            }
        }
    }
    return dp[n][capacity]
}

// 0/1 Knapsack Space-Optimized 1D DP: O(W) space
func knapsack1D(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]
        // RIGHT-TO-LEFT LOOP: prevents using current item i twice!
        for w := capacity; w >= wt; 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("2D Max Value:", knapsack2D(weights, values, cap)) // Output: 16
    fmt.Println("1D Max Value:", knapsack1D(weights, values, cap)) // Output: 16
}

Core 0/1 Mechanics & Backward Updating

0/1 Definition -> Use Each Item AT MOST ONCE
2D Matrix -> dp[i][w] reads dp[i-1][w - weight] (Previous Row)
1D Array -> Loop capacity w = W down to weight (Right-to-Left / Backwards)
Partition Equal Subset Sum -> Target = total / 2 (0/1 Subset Sum)
Last Stone Weight II / Min Diff -> Target = largest S1 <= total / 2; ans = total - 2*S1
Target Sum -> Target Positive Sum P = (total + target) / 2

0/1 Knapsack Variants & Advanced Optimizations

Common Interview Mistakes

• • Iterating 1D capacity loop forwards (Left-to-Right), accidentally reusing the same item multiple times.
• • Reading current row dp[i][w - weight] in 2D take transition instead of previous row dp[i-1][w - weight].
• • Updating DP values when item weight > current capacity w (item does not fit in capacity w).
• • Using 0 base initialization for counting/boolean problems instead of dp[0] = 1 or dp[0] = true.
• • Failing to handle zeroes in Target Sum / Subset counting (zeroes double the valid subset count choices).
• • Assuming 0/1 Knapsack is polynomial in N (it is pseudo-polynomial in capacity W).
• • Attempting 1D capacity DP when W = 10^9 without checking constraint bounds (causes Memory Limit Exceeded).
• • Failing to check odd total sum in Partition Equal Subset Sum (odd sum can never be divided by 2).
• • Confusing 0/1 Knapsack (single use per item) with Unbounded Knapsack (unlimited item reuse).

Interview Rules

Single-use item selection + capacity? → 0/1 Knapsack DP
Rule 1                              → Define dp[i][w] state meaning explicitly
Rule 2                              → 2D Matrix: dp[i][w] = max(dp[i-1][w], val + dp[i-1][w-wt])
Rule 3                              → 1D Array: Loop capacity w = W down to weight (Right-to-Left)
Rule 4                              → Partition Equal Subset: Target = total / 2
Rule 5                              → Target Sum: Target positive subset sum P = (total + target) / 2
Rule 6                              → Massive 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: Every item gets one decision only—take it once or skip it—so when you compress to 1D DP, update capacity backwards to prevent using the same item again.

0/1 Rule: Each item usable AT MOST ONCE
1D Array: Loop Capacity RIGHT-TO-LEFT (w = W down to wt)
2D Matrix: Take reads Previous Row dp[i-1][w-wt]
Partition Equal Subset: Target = total / 2
Target Sum: Target sum P = (total + target) / 2
Pseudo-Polynomial: Time = O(N * W), Space = O(W)