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.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Approach 1D tabulation

• just similar to partition sum just in here if it is possible for dp[j] then it remains true
• Few things to know like if totals sum is odd then not possible because no number times 2 equals an odd number
• The only partition sum that would give result would be obviously half now the question is what two partition can give that
• O(n*target), O(target)

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num: nums)
            total += num;
 
        if ((total & 1) == 1)
            return false;
 
        int target = total / 2;    
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
 
        for (int num: nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
 
        return dp[target];
    }
}

class Solution {
    Boolean[][] dp;
 
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
 
        int target = sum / 2;
        dp = new Boolean[nums.length][target + 1];
 
        return solve(nums, 0, target);
    }
 
    public boolean solve(int[] arr, int i, int target) {
        if (target == 0) return true;
        if (i == arr.length || target < 0) return false;
 
        if (dp[i][target] != null) return dp[i][target];
 
        boolean take = solve(arr, i + 1, target - arr[i]);
        boolean skip = solve(arr, i + 1, target);
 
        return dp[i][target] = take || skip;
    }
}
 

class Solution {
    Boolean[][] dp;
 
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
 
        int target = sum / 2;
        dp = new Boolean[nums.length][target + 1];
 
        return solve(nums, 0, target);
    }
 
    public boolean solve(int[] arr, int i, int target) {
        if (target == 0) return true;
        if (i == arr.length || target < 0) return false;
 
        if (dp[i][target] != null) return dp[i][target];
 
        boolean take = solve(arr, i + 1, target - arr[i]);
        boolean skip = solve(arr, i + 1, target);
 
        return dp[i][target] = take || skip;
    }
}