Subset Sum

1. 1.Subset Sum
   Boolean 0/1 DP: dp[s] = dp[s] || dp[s - num] updated backwardsmedium
2. 2.Partition Equal Subset Sum
   Check total sum even; solve Subset Sum for target = sum/2medium
3. 3.Target Sum
   Transform P = (total + target)/2; count subsets with sum Pmedium
4. 4.Last Stone Weight II
   Find max subset sum S1 <= total/2; final diff = total - 2*S1medium
5. 5.Minimum Subset Sum Difference
   Find largest reachable S1 <= total/2; min diff = total - 2*S1medium
6. 6.Count Subsets With Given Sum
   0/1 counting DP: dp[s] += dp[s - num] updated backwardsmedium
7. 7.Number of Subsets With Given Difference
   Count subsets for target sum S1 = (total + diff)/2medium
8. 8.Equal Sum Partition
   Boolean Subset Sum mapping for half total summedium
9. 9.Split Array Into Two Equal Sum Sets
   Check if total is even and subset sum target = sum/2 is reachablemedium
10. 10.Ones and Zeroes — multi-capacity relation
    Multi-dimensional 0/1 Subset Sum DP: dp[z][o] updated backwardsmedium
11. 11.Tallest Billboard — advanced relation
    State difference DP: dp[diff] tracking max lower heighthard
12. 12.Matchsticks to Square — related partition thinking
    Backtracking / Bitmask DP partitioning array into 4 equal sidesmedium
13. 13.Partition to K Equal Sum Subsets — advanced
    Backtracking with Bitmask DP partitioning array into K equal sum subsetsmedium
14. 14.Closest Subsequence Sum — advanced
    Meet-in-the-Middle split N/2 + binary search for closest targethard
15. 15.Meet-in-the-Middle Subset Sum
    Split array into 2 halves (N <= 40) when target T is hugehard

1. 16.Subset Sum Using Bitset
   Bitwise shift: dp |= (dp << num) for 64x parallel speeduphard
2. 17.Return One Valid Subset
   Backtrack 2D matrix: compare dp[i][s] == dp[i-1][s] to recover itemsmedium
3. 18.Count Number of Valid Subsets
   Subset sum counting DP with zeroes handlingmedium
4. 19.Minimum Number of Elements to Reach Target
   Unbounded or 0/1 min items count DPmedium
5. 20.Subset Sum With Large Target — alternative approaches
   Meet-in-the-Middle, Bitset, or Hash Set reachability comparisonhard

1. Need to choose some elements to make target?Subset Sum DP
2. Each number usable only once?0/1 Knapsack (Right-to-Left loop)
3. Need only possible / impossible?Boolean DP (dp[s] = dp[s] || dp[s-num])
4. Using 1D DP array?Loop target RIGHT -> LEFT (sum = target down to num)
5. Base Case for Target 0?dp[0] = true (empty set sum = 0)

package main

import "fmt"

// Subset Sum 1D Boolean DP: O(N * Target) time, O(Target) space
func subsetSum(nums []int, target int) bool {
    dp := make([]bool, target+1)
    dp[0] = true // Base case: Empty set has sum 0

    for _, num := range nums {
        // RIGHT-TO-LEFT LOOP: prevents using num twice!
        for s := target; s >= num; s-- {
            if dp[s-num] {
                dp[s] = true
            }
        }
    }
    return dp[target]
}

// Partition Equal Subset Sum: Check even total sum + Subset Sum
func canPartition(nums []int) bool {
    totalSum := 0
    for _, num := range nums { totalSum += num }

    if totalSum%2 != 0 {
        return false // Odd total sum can never be divided equally
    }
    return subsetSum(nums, totalSum/2)
}

func main() {
    nums := []int{1, 5, 11, 5}
    fmt.Println("Subset Sum (Target 11):", subsetSum(nums, 11)) // Output: true
    fmt.Println("Can Equal Partition:", canPartition(nums))       // Output: true
}

Core Subset Mechanics & Reachable Set Expansion

Subset Sum Base Case -> dp[0] = true (Empty Set Sum = 0)
1D Array Update -> Loop target s = target down to num (Right-to-Left)
Partition Equal Subset Sum -> Target = total / 2 (Check total%2 == 0)
Last Stone Weight II / Min Diff -> Target = largest S1 <= total / 2; ans = total - 2*S1
Target Sum -> Target Positive Sum P = (total + target) / 2
Bitset Optimization -> dp |= (dp << num) for 64x parallel speedup

Subset Sum Variants & Advanced Optimizations

Common Interview Mistakes

• • Iterating 1D target loop forwards (Left-to-Right), accidentally reusing the same number multiple times.
• • Forgetting base case initialization dp[0] = true (empty set sum = 0), leaving all states unreachable.
• • Failing to check odd total sum in Partition Equal Subset Sum (odd sum can never be divided by 2).
• • Mishandling zero values in Subset Sum counting (zeroes double valid subset count choices).
• • Assuming classic 0...target boolean DP works with negative numbers without index offset shifting.
• • Confusing Subset Sum (each number used once) with Coin Change (coins reusable unlimited times).
• • Attempting 1D target DP when target T = 10^9 without checking constraint bounds (causes Memory Limit Exceeded).
• • Assuming element order matters (subsets [2,3] and [3,2] represent the exact same subset selection).
• • Building full DP table when target > totalSum (impossible to form sum larger than all numbers combined).

Interview Rules

Choose elements to reach exact target? → Subset Sum DP
Rule 1                                 → Define dp[s] boolean state meaning explicitly
Rule 2                                 → Base Case: dp[0] = true (empty set sum = 0)
Rule 3                                 → 1D Array: Loop target s = target down to num (Right-to-Left)
Rule 4                                 → Partition Equal Subset: Target = total / 2 (Odd sum = false)
Rule 5                                 → Target Sum: Positive subset target P = (total + target) / 2
Rule 6                                 → Massive T = 10^9: Use Meet-in-the-Middle or Bitset optimization
Time Complexity                        → O(N * Target) (Pseudo-Polynomial)
Space Complexity                       → O(N * Target) 2D Table or O(Target) 1D Boolean Array

💡 Golden Rule: Track which sums are reachable, and for each number update those sums backwards so that the current number can contribute at most once.

Subset Sum Goal: Can any element subset sum to target?
Base Case: dp[0] = true (Empty Set Sum = 0)
1D Array: Loop Target RIGHT-TO-LEFT (s = target down to num)
Partition Equal Subset: Target = total / 2
Target Sum: Target positive subset sum P = (total + target) / 2
Bitset Acceleration: reachable |= (reachable << num)
Pseudo-Polynomial: Time = O(N * T), Space = O(T)