Partition equal Subset Sum

Question:

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.

Solution:

• Same question as Subset Sum Equal To K, just check if the total Sum of array can be divided by 2.
• If yes, then find a subset equal to that totalSum/2.
• If no, return false.

Recursive and DP Solution

DP solution TC and SC Time Complexity: O(n * target), where n is the number of elements in the array and target is half of the total sum. Space Complexity: O(target), since we are using a 1D array for the dynamic programming solution.

public class PartitionEqualSubsetSum {
 
public boolean canPartitionRecursive(int[] nums, int n, int target) {
     // Base cases
     if (target == 0) return true; // Found a subset with the target sum
     if (n == 0 || target < 0) return false; // No more elements or target is invalid
     
     // Choice to pick or not pick the current element nums[n-1]
     boolean pick = canPartitionRecursive(nums, n - 1, target - nums[n - 1]); // Pick the element
     boolean notPick = canPartitionRecursive(nums, n - 1, target); // Don't pick the element
     
     // Return true if either pick or notPick leads to a valid subset
     return pick || notPick;
 }
 
 public boolean canPartitionDP(int[] nums) {
     int totalSum = 0;
     
     // Calculate the total sum of the array
     for (int num : nums) {
         totalSum += num;
     }
     
     // If the total sum is odd, we can't partition it into two equal subsets
     if (totalSum % 2 != 0) {
         return false;
     }
     
     int target = totalSum / 2;
     
     // Create a DP array to store whether a specific sum can be achieved
     boolean[] dp = new boolean[target + 1];
     dp[0] = true; // We can always achieve sum 0 by choosing no elements
     
     // Iterate over each number in the array
     for (int num : nums) {
         // Update the DP array in reverse order
         for (int i = target; i >= num; i--) {
             dp[i] = dp[i] || dp[i - num]; // not pick || pick decision
         }
     }
     
     // The answer will be stored in dp[target]
     return dp[target];
 }
 
 public static void main(String[] args) {
     PartitionEqualSubsetSum solution = new PartitionEqualSubsetSum();
     
     int[] nums1 = {1, 5, 11, 5};
     System.out.println(solution.canPartitionDP(nums1)); // Output: true
     
     int[] nums2 = {1, 2, 3, 5};
     System.out.println(solution.canPartitionDP(nums2)); // Output: false
 }
}

Space Optimized

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int i = 0; i < nums.length; i++){
            total += nums[i];
        }
 
        if(total % 2 != 0){
            return false;
        }
 
        int targetSum = total/2; 
 
        return subsetSumToK(nums.length, targetSum, nums);
    }
 
    public static boolean subsetSumToK(int n, int target, int arr[]){
	    //2-D which will contain indexes from 0 to n-1 and target from 0 to target
		boolean[] prev = new boolean[target + 1];
		boolean[] curr = new boolean[target + 1];
	
		//Base case
		prev[0] = true;//true for target zero
		for(int j = 1; j <= target; j++){
			prev[j] = false;
		}
		
		curr[0] = true; // A sum of 0 is always possible
		for(int j = 1; j <= target; j++){
			curr[j] = false; //baaki toh assign false, because these will be filled in the below loop
		}
	
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= target; j++){
				//If we don't include the current element
				curr[j] = prev[j]; //Whatever the answer was till the last element
	
				//if the current target is greater than current element then only we can subtract the target
				//and check at the previous result of previous row if it was achieved or not.
				if(j >= arr[i - 1]){
					curr[j] = curr[j] || prev[j - arr[i - 1]];
				}
			}
			prev = curr.clone();
		}
	
		return prev[target];
	}
}