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.

Examples

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.

Similar problems

Partition to K Equal Sum Subsets Problem

Solution

Let’s say that the array nums can be broken down into two subsets S1 and S2 of equal sums. We can observe the following things

// Sum of all the numbers in subset S1 + Sum of all the numbers in subset S2 = Sum of all the numbers in the array
Sum(S1) + Sum(S2) = Sum(nums)

// If Sum(S1) and Sum(S2) is equal
2*Sum(S1) = Sum(nums)

Sum(S1) = Sum(nums)/2

The problem reduces to finding a subset of sum Sum(nums)/2 in the array. If we can find a subset of sum Sum(nums)/2 then we can definitely partition the array into two subsets of equal sums.

Note that I have already explained the solution approach for the Subset Sum Problem 1 - Is there a subset?. So I will directly jump to the code.

Method 1 - Recursive Solution

class Solution {
	public boolean canPartition(int[] nums) {
		int sum = Arrays.stream(nums).sum();
		// if sum is odd, we cant divide in equal 2 halfs
		if (sum % 2 == 1) {
			return false;
		}

		return dfs(nums, sum / 2, nums.length - 1);
	}

	private boolean dfs(int[] nums, int sum, int n) {
		if (sum == 0) {
			return true;
		}

		if (n == 0) {
			return false;
		}

		if (nums[n - 1] > sum) {
			return dfs(nums, sum, n - 1);
		}

		return dfs(nums, sum - nums[n - 1], n - 1) || dfs(nums, sum, n - 1);
	}
}

Complexity

  • ⏰ Time complexity: O(2^n), where n is number of elements in array, as run the DFS to find set of n elements whose sum is equal to sum(nums)/2.
  • 🧺 Space complexity: O(n) for recursion stack

Method 2 - Dynamic Programming Top Down Solution (Memoization)

class Solution {
    private Boolean[][] dp;
    public boolean canPartition(int[] values, int targetSum, int n) {
        dp = new Boolean[targetSum + 1][n + 1];
        return hasSubsetSumRecur(values, targetSum, n);
    }

    private boolean dfs(int[] values, int targetSum, int n) {
        if (targetSum == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }

        if (subsetSumMem[targetSum][n] != null) {
            return dp[targetSum][n];
        }

        if (values[n - 1] > targetSum) {
            dp[targetSum][n] = hasSubsetSumRecur(values, targetSum, n - 1);
        } else {
            dp[targetSum][n] = hasSubsetSumRecur(values, targetSum - values[n - 1], n - 1)
                    || hasSubsetSumRecur(values, targetSum, n - 1);
        }

        return dp[targetSum][n];
    }


}

Method 3 - Dynamic Programming Bottom up Solution

class Solution {
    private static boolean hasSubsetSum(int[] nums, int targetSum) {
        int n = nums.length;
	    // 
        boolean[][] dp = new boolean[targetSum + 1][n + 1];
        subsetSum[0][0] = true;// without any elements, sum of 0 is easily acheived

        for (int i = 1; i <= targetSum; i++) {
            for (int j = 1; j <= n; j++) {
	            // if number is larger then sum, we skip this number
                if (nums[j - 1] > i) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i - nums[j - 1]][j - 1] || dp[i][j - 1];
                }
            }
        }

        return subsetSum[targetSum][n];
    }

}