416. Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

https://leetcode.com/problems/partition-equal-subset-sum/solutions/462699/whiteboard-editorial-all-approaches-explained/

DP

Base Case: target (sum remaining) = 0

DFS memo n choices

public boolean canPartition(int[] nums) {
    int total = 0;
    for(int n: nums) total += n;
    if(total % 2 != 0) return false;

    int target = total / 2;
    Boolean[][] memo = new Boolean[nums.length + 1][target + 1];
    
    return dfs(nums, target, 0, memo);
}
boolean dfs(int[] nums, int target, int index, Boolean[][] memo){
    if(memo[index][target] != null) return memo[index][target];
    if(target == 0) return (memo[index][target] = true);

    for(int i = index; i < nums.length; i++)
        if(nums[i] <= target){
            memo[i][target] = dfs(nums, target - nums[i], i + 1, memo);
            if(memo[i][target]) return true;
        }
    
    return (memo[index][target] = false);
}

DFS memo 2 choices (skip or include)

public boolean canPartition(int[] nums) {
    int total = 0;
    for(int n: nums) total += n;
    if(total % 2 != 0) return false;

    int target = total / 2;
    Boolean[][] memo = new Boolean[nums.length][target + 1];

    return dfs(nums, target, 0, memo);
}
// returns true if we can reach "target" from the set of numbers whose indices >= "pos"
boolean dfs(int[] nums, int target, int pos, Boolean[][] memo){
    if(pos == nums.length || target < 0) return false;

    if(memo[pos][target] != null) return memo[pos][target];

    if(target == 0) return true;
    
    boolean skip = dfs(nums, target, pos + 1, memo);
    boolean include = dfs(nums, target - nums[pos], pos + 1, memo);

    return (memo[pos][target] = skip || include);
}

DP

• rows represent num[i]
• cols represent amount from 0 to sum / 2
• col 0 is true (we can just not put anything)

2D DP

• dp[i + 1][j] = dp[i][j] || dp[i][j - n]

//                skip num    include num (target reduces by num)
// dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]]
public boolean canPartition(int[] nums) {
    int total = 0;
    for(int n: nums) total += n;
    if(total % 2 != 0) return false;

    int target = total / 2;
    // dp[i][j] -> Can we reach sum j from numbers upto index i-1
    boolean[][] dp = new boolean[nums.length + 1][target + 1];

    for(int i = 0; i < nums.length; i++)
        for(int j = 1; j <= target; j++){
            if(nums[i] == j) dp[i + 1][j] = true;
            // n > j (we can't include this num)
            else if(j - nums[i] < 0) dp[i + 1][j] = dp[i][j];

            else dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]];
        }
    
    return dp[nums.length][target];
}

2 row DP

• next[j] = prev[j] || prev[j - n]

// dp[i][j] -> Can we reach sum j from numbers upto index i-1

//                skip num    include num (target reduces by num)
// dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]]
public boolean canPartition(int[] nums) {
    int total = 0;
    for(int n: nums) total += n;
    if(total % 2 != 0) return false;

    int target = total / 2;
    boolean[] curr = new boolean[target + 1];
    boolean[] prev = new boolean[target + 1];

    for(int i = 0; i < nums.length; i++){
        for(int j = 1; j <= target; j++){
            if(nums[i] == j) curr[j] = true;
            // n > j (we can't include this num)
            else if(j - nums[i] < 0) curr[j] = prev[j];

            else curr[j] = prev[j] || prev[j - nums[i]];
        }
        prev = curr.clone();
    }
    
    return curr[target];
}

1 row DP

• dp[j] = dp[j] || dp[j - n]

// dp[i][j] -> Can we reach sum j from numbers upto index i-1

//                skip num    include num (target reduces by num)
// dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]]
public boolean canPartition(int[] nums) {
    int total = 0;
    for(int n: nums) total += n;
    if(total % 2 != 0) return false;

    int target = total / 2;
    boolean[] dp = new boolean[target + 1];

    for(int i = 0; i < nums.length; i++){
        // iterate from reverse to avoid overwriting current values
        for(int j = target; j >= 1; j--){
            if(nums[i] == j) dp[j] = true;
            // if num[i] is selected, remaining target reduces by num[i]
            else if(j - nums[i] >= 0)
                dp[j] = dp[j] || dp[j - nums[i]];
        }
    }

    return dp[target];
}