Subset Partition

These problems are variations of the 0/1 Knapsack problem. Instead of maximizing value, we are often asking a boolean question: “Is it possible to reach a specific sum?”

1. Subset Sum Problem

Problem Statement: Given a set of non-negative integers nums and a target value target, determine if there is a subset of nums that sums up to target.

Recurrence Relation

Let dp[i][s] be a boolean value indicating if sum s is possible using the first i numbers.

• Exclude nums[i]: If dp[i-1][s] is true, then dp[i][s] is true (we just ignore the new number).
• Include nums[i]: If s ≥ nums[i] and dp[i-1][s - nums[i]] is true, then dp[i][s] is true (we add the new number to a valid previous sum).

dp[i][s] = dp[i-1][s] || dp[i-1][s - nums[i]]

Interactive Visualization

Let’s check if we can form the Target Sum: 7 using the numbers [2, 3, 4].

[!TIP] Try it yourself: Click “Check Possibility” to fill the table. Green cells mean “Yes, possible”. The arrows show how a True value propagates.

Ready

Code Implementation: Subset Sum

// Java
public class SubsetSum {
  public boolean canPartition(int[] nums, int target) {
    int n = nums.length;
    boolean[][] dp = new boolean[n + 1][target + 1];

    // Base case: sum 0 is always possible (empty set)
    for (int i = 0; i <= n; i++) {
      dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
      for (int s = 1; s <= target; s++) {
        if (s >= nums[i - 1]) {
          dp[i][s] = dp[i - 1][s] || dp[i - 1][s - nums[i - 1]];
        } else {
          dp[i][s] = dp[i - 1][s];
        }
      }
    }
    return dp[n][target];
  }
}

// Go
func CanPartition(nums []int, target int) bool {
  n := len(nums)
  dp := make([][]bool, n+1)
  for i := range dp {
    dp[i] = make([]bool, target+1)
    dp[i][0] = true // Base case
  }

  for i := 1; i <= n; i++ {
    for s := 1; s <= target; s++ {
      if s >= nums[i-1] {
        dp[i][s] = dp[i-1][s] || dp[i-1][s-nums[i-1]]
      } else {
        dp[i][s] = dp[i-1][s]
      }
    }
  }
  return dp[n][target]
}

2. Partition Equal Subset Sum

Problem Statement: Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Insight: This is exactly the Subset Sum problem! If the total sum of the array is S, we need to find a subset with sum S/2. If S is odd, it’s impossible.

Code Implementation

// Java
public class PartitionEqualSubsetSum {
  public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;

    if (sum % 2 != 0) return false;

    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    // 1D Space Optimization (iterating backwards)
    for (int num : nums) {
      for (int i = target; i >= num; i--) {
        dp[i] = dp[i] || dp[i - num];
      }
    }

    return dp[target];
  }
}

// Go
func CanPartitionEqualSubset(nums []int) bool {
  sum := 0
  for _, num := range nums {
    sum += num
  }

  if sum % 2 != 0 {
    return false
  }

  target := sum / 2
  dp := make([]bool, target+1)
  dp[0] = true

  // 1D Space Optimization
  for _, num := range nums {
    for i := target; i >= num; i-- {
      if dp[i-num] {
        dp[i] = true
      }
    }
  }

  return dp[target]
}

---

3. Deep Dive Strategy Lab: Subset Partition

Intuition Through Analogy

Think of this chapter like budget planning across months. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?