Problem Explanation

Given a non-empty array that contains only positive integers, the task is to find out if it is possible to divide the array into two subsets such that the sum of the elements of both the subsets is equal.

Example

Let's consider an example where the input array is [1, 5, 11, 5].

We can divide this array into two subsets, [1, 5, 5] and [11], such that the sum of elements in both subsets is 11. So, the output in this case will be true.

Approach

First, Calculate the sum of elements in the array. If the sum is odd, return immediately with a result of false because it's impossible to split an array with an odd sum into two parts with equal sums.

Otherwise, proceed to use the Knapsack problem to check if there is a subset in this array that adds up to sum/2. If there is, this means we can divide this array into two subsets with equal sums, and the result is true; otherwise, the result is false.

Example

Let's consider the set [1, 5, 11, 5] to walk through the solution. First, we calculate the sum of the array, which is 22. Since this number is even, it is potentially possible to divide the array into two subsets with equal sums. We need to see if there's a subset in this array that adds up to sum/2, or 11.

We create an array dp that keeps track of the possible sums from 0 to 11. We start with all false values, except for dp[0], because zero can be obtained by not selecting anything.

For each number, we update dp[i] to true if there is a number in the array which equals to or less than i.

At the end of the procedure, dp[11] is true, indicating that it's possible to obtain the sum 11 by adding some numbers from the array. Thus, we can divide the array into two subsets with equal sums, and return true.

Solutions

Python

1
2python
3class Solution:
4    def canPartition(self, nums):
5        _sum = sum(nums)
6        
7        # Impossible to split an odd sum equally
8        if _sum % 2 != 0:
9            return False
10        
11        target = _sum // 2
12        dp = [False] * (target + 1)
13        dp[0] = True
14        
15        for num in nums:
16            for i in range(target,num-1,-1):
17                dp[i] = dp[i] or dp[i-num]
18
19        return dp[target]

Java

1
2java
3class Solution {
4    public boolean canPartition(int[] nums) {
5        int sum = 0;
6        for (int num: nums) {
7            sum += num;
8        }
9        if(sum%2 == 1){
10            return false;
11        }
12        sum = sum/2;
13        boolean[] dp = new boolean[sum + 1];
14        dp[0] = true;
15        for(int num:nums){
16            for(int j = sum; j>= num; j--){
17                dp[j] = dp[j] || dp[j-num];
18            }
19        }
20        return dp[sum];
21    }
22}

JavaScript

1
2javascript
3var canPartition = function(nums) {
4    let sum = nums.reduce((acc, val) => acc + val);
5    if (sum % 2 !== 0) return false;
6    let target = sum / 2;
7    let dp = new Array(target + 1).fill(false);
8    dp[0] = true;
9    for (let num of nums) {
10        for (let i = target; i >= num; i--) {
11            dp[i] = dp[i] || dp[i - num];
12        }
13    }
14    return dp[target];
15};

C++

1
2cpp
3class Solution {
4public:
5    bool canPartition(vector<int>& nums) {
6        int sum = accumulate(nums.begin(), nums.end(), 0);
7        if (sum % 2 != 0) return false;
8        sum /= 2;
9        
10        vector<bool> dp(sum+1, false);
11        dp[0] = true;
12        for (int num : nums) {
13            for (int i = sum; i >= num; i--) {
14                dp[i] = dp[i] || dp[i - num];
15            }
16        }
17        return dp[sum];
18    }
19};

C#

1
2csharp
3public class Solution {
4    public bool CanPartition(int[] nums) {
5        int sum = 0;
6        foreach (var num in nums) { sum += num; }
7        if (sum % 2 != 0) { return false; }
8        sum /= 2;
9        
10        bool[] dp = new bool[sum + 1];
11        dp[0] = true;
12        foreach (var num in nums) {
13            for (int i = sum; i >= num; i--) {
14                dp[i] = dp[i] || dp[i - num];
15            }
16        }
17        return dp[sum];
18    }
19}

Each of the solutions above first checks if the total sum is odd. If it is, there is no way to separate the array into two equal subsets and the function immediately returns false.

If the total sum is even, the problem boils down to finding a subset in nums which sums up to sum / 2. This is a 0/1 knapsack problem, where we are trying to fill a sack of capacity sum / 2 to the fullest. If we can do this, we can partition the array into two equal subsets, otherwise we can't.

We do this in the inner loop, in a bottom-up manner, by iterating from i to num (the current number). If dp[i] was false before the loop and becomes true inside the loop, then there exists a subset which sums up to i (including the current number, since we subtract it in dp[i - num]).So, at every iteration, we are essentially filling the dp array with the possible sums, which we can get by selecting some numbers in the nums array. If at the end of the iterations, dp[sum / 2] is true, then there exists a subset which sums up to sum / 2.

Otherwise, if dp[sum / 2] is still false, then we cannot get a sum of sum / 2 by selecting some numbers from the nums array, and hence, we cannot partition the array into two equal subsets.

The overall time complexity of each solution above is O(n * sum); n being the count of numbers and sum being the total sum of the numbers. The space complexity is O(sum), as we only need a boolean dp array of length sum + 1.

It is quite clear that, with such an approach, we can solve the problem efficiently. Even though the problem of partitioning an array into two subsets with equal sums seems complex at first, breaking it down into simpler sub-problems makes the process much less daunting.