The key to understanding this problem is this. You need an array that will keep track of the possible sums you can get by adding the numbers in the nums array in various ways. For example, if the nums array is [1, 2, 3], the combination sum array will be [true, true, true, true, true, true, true]. Here’s how the combination sum array works. Each index represents whether we can arrive at that number by adding the numbers in the nums array various ways. For example, index 1 in the combination sum array is true because we can arrive at the number 1 by just using the number 1 in the nums array. Index 2 in the combination sum array is true because we can arrive at the number 2 by just using the number 2 in the nums array. Fast forward a bit, and index 6 is true because we can arrive at the number 6 by adding all of the numbers in the nums array (1 + 2 + 3). We can use the same logic for every index in the combination sum array.
Now that we understand that, we can apply it to this problem. The question asks if we can split up the nums array in such a way that we have subsets whose elements have equal total values. For example, if we have the nums array [1, 5, 11, and 5], our result would be true because we can split it up into [1, 5, 5] (whose values total 11) and [11] (whose value also equals 11). The sum of the elements in both subsets equal 11. So how would we know if we can split it up into equal subsets? By testing if any subset equals half the sum of all elements in the nums array. Going back to the last example, the sum of all of the elements in the nums array is 22. Half of that is 11, so that’s our goal — to find a subset that totals 11. If we find one, it means there is another subset that equals the same thing.
So now we create a combination sum array (the true/false array we mentioned in the first paragraph) from 0 to half the sum of the elements in the nums array. Meaning if our nums array is [1, 2, 3], its total equals 6, so we create an array from 0 to half of 6 (which is 3). This would initially look like this: [true, false, false, false]. Note that the 0th index is always set to true. Now our only real job is to determine if the final index in the combination sums array will ever be true. If it’s true, it means there exists a combination of numbers in our nums array that equals half of the total of all of its elements. This is exactly what we’re looking for.
Now comes the hard part. We have to determine which combination sums are possible given the numbers in our nums array. To do this, we iterate over our combination sums array from right to left, and over our nums array from left to right. For every value in our nums array, we have to iterate right to left over our combination sums array to determine if we can arrive at that index using a combination of the elements in our nums array. And remember that at this point, every value in our combination sums array is false (except for the first index) — “false” meaning we have not found a combination of numbers in our nums array that adds up to that index of our combination sum array. So how to we flip the “false” values to “true”?
To do this, we need two pieces of information. The first is if the index in our combination sums array is already true. If it’s true, it means we have already seen that combination sum before. In that case, we just move on to the next element in our combination sum array. If it’s false, we have to determine if it should be true. It should be true if we can arrive at the target sum. How do we know that? Remember that we are on a certain number in the nums array. Pretend it’s a 2. Now imagine that the target sum (the index we’re on in the combination sum array) is 3. How could we get the number 3 using the number 2. Well, we know that 2 + 1 = 3. So if we also had the number 1, we’d flip the combination sum index to true. Meaning, we are at the number 2 in our nums array. We look at index 1 in our combination sums array. If that is true, we know that we can flip index 3 in our combination sum array to true because we have the number 2 plus the number 1 we need to come up with the target value of 3.
We repeat this process, flipping the “false” indeces to “true” for every combination sum that’s possible. After we’re done, we check the last index of the combination sum array. Our question’s result equals its value. Why? Again, because it represents the combination sum that shows us whether there are any subsets whose elements total half of the value. If it’s false, our entire answer is false. If it’s true, our entire answer is true.
AFFILIATE LINKS
Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard
Here is the full implementation.
/**
* @param {number[]} nums
* @return {boolean}
*/
let canPartition = function(nums) {
let sum = 0;
for (let num of nums) {
sum += num; // find the total of the values in the nums array
}
if (sum % 2 === 1) {
return false; // if the value of the nums array is odd, return false
}
/* reset sum to half of the total of the values in the nums array. this will be used to determine if any subsets in the array equal half of the values in the array */
sum = sum / 2;
/* make an array with values from 0 to sum. this represents the possible combination sums */
let combos = new Array(sum + 1);
/* make each value in the combos array false */
combos.fill(false);
/* reset the first value in the combos array to true. we do this so that each number in the nums array will have a complement of zero */
combos[0] = true;
for (let num of nums) {
/* iterate backwards from the target sum to the current index of the nums array */
for (let i = sum; i >= num; i--) {
/* the target sum will be true if a) the target sum is already true or b) we can hit the target sum by using the current number's complement */
combos[i] = combos[i] || combos[i - num];
}
}
/* return whether the final index in the combination sum array is true. this can only be true if there are two subsets with equal values */
return combos[sum];
};