Solution For Partition Equal Subset Sum

Problem:

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.

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.

Solution:

To solve this problem, we can use dynamic programming. We can start by calculating the sum of all elements in the input array. If the sum of all elements is odd, we can’t divide the array into two subsets with equal sums, so we return false. If the sum of all elements is even, we can divide the array into two subsets with equal sums. We can then use dynamic programming to solve the problem.

We can create a boolean two-dimensional array dp, where dp[i][j] represents whether it is possible to construct a subset of the first i elements of the input array, whose sum is j. If dp[nums.length][sum_of_all_elements / 2] is true, we return true, otherwise we return false.

To fill the dp array, we can follow these steps:
1. Initialize dp[i][0] to true, because we can always create a subset of sum 0 with any set of elements.
2. Initialize dp[0][j] to false, because we can’t create a subset using an empty set of elements.
3. For each element nums[i-1], we check if we can create a subset of sum j using either nums[i-1] or not. We can use it only if nums[i-1] is less than or equal to j. Otherwise, we can’t consider it.
4. If we can create a subset of sum j without using nums[i-1], we can just copy the value from dp[i-1][j]. Otherwise, we need to check if we can create a subset of sum j-nums[i-1] using the first i-1 elements. If yes, then we can create a subset of sum j using the first i-1 elements and nums[i-1].

Here’s the Java code for the solution:

class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 == 1) {
return false;
}
sum /= 2;
boolean[][] dp = new boolean[nums.length + 1][sum + 1];
for (int i = 0; i <= nums.length; i++) {
dp[i][0] = true;
}
for (int j = 1; j <= sum; j++) {
dp[0][j] = false;
}
for (int i = 1; i <= nums.length; i++) {
for (int j = 1; j <= sum; j++) {
if (nums[i – 1] > j) {
dp[i][j] = dp[i – 1][j];
} else {
dp[i][j] = dp[i – 1][j] || dp[i – 1][j – nums[i – 1]];
}
}
}
return dp[nums.length][sum];
}
}

Time complexity: O(n * sum), where n is the length of the input array and sum is the sum of all elements in the input array.
Space complexity: O(n * sum), we use a two-dimensional dp array of size (n+1) * (sum+1).

Step by Step Implementation For Partition Equal Subset Sum

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

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # base case
        if sum(nums) % 2 != 0:
            return False
        
        # initialize a 2D array with all False values
        dp = [[False for _ in range(len(nums))] for _ in range(sum(nums)//2+1)]
        
        # set the first column to True (can always get a sum of 0)
        for i in range(len(dp)):
            dp[i][0] = True
        
        # iterate through the array
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                # set the current value to the value above it
                dp[i][j] = dp[i-1][j]
                # if the current value is less than or equal to the current sum,
                # we can check if we can get the current sum by adding the current value
                if i >= nums[j-1]:
                    dp[i][j] = dp[i][j] or dp[i-nums[j-1]][j-1]
        
        # return the bottom right value in the array (whether we can get the sum of the entire array)
        return dp[-1][-1]

var canPartition = function(nums) {
    // edge case
    if (nums.length === 0) {
        return true;
    }
    
    // get sum of all elements
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    
    // sum cannot be odd
    if (sum % 2 === 1) {
        return false;
    }
    
    // initialize dp array
    const dp = new Array(sum / 2 + 1).fill(false);
    dp[0] = true;
    
    // fill dp array
    for (let i = 0; i < nums.length; i++) {
        for (let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    
    // return whether partition is possible
    return dp[sum / 2];
};

class Solution {
public:
    bool canPartition(vector& nums) {
        int sum = 0; 
        for(int i: nums)
            sum += i;
        if(sum % 2 != 0)
            return false;
        sum /= 2;
        vector dp(sum+1, false);
        dp[0] = true;
        for(int i = 0; i < nums.size(); i++){
            for(int j = sum; j >= nums[i]; j--){
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[sum];
    }
};

public bool CanPartition(int[] nums) { // check edge cases if (nums == null || nums.Length == 0) { return false; } // create an array to track whether a sum can be made int sum = 0; foreach (int num in nums) { sum += num; } if (sum % 2 != 0) { return false; } // create a 2D array to track whether a sum can be made // using the given numbers sum /= 2; bool[,] dp = new bool[nums.Length, sum + 1]; // fill in the first column for (int i = 0; i < nums.Length; i++) { dp[i, 0] = true; } // fill in the first row for (int j = 1; j <= sum; j++) { dp[0, j] = nums[0] == j; } // fill in the rest of the table for (int i = 1; i < nums.Length; i++) { for (int j = 1; j <= sum; j++) { if (dp[i - 1, j]) { dp[i, j] = dp[i - 1, j]; } else if (nums[i] <= j) { dp[i, j] = dp[i - 1, j - nums[i]]; } } } return dp[nums.Length - 1, sum]; }