Problem overview
The method canPartition receives a vector<int> named nums of positive integers and returns true when the numbers can be split into two groups with equal sums, false otherwise. Every number goes into exactly one group, and repeated values are separate numbers: each copy goes into one group.
For [1, 5, 11, 5] the answer is true: [1, 5, 5] and [11] both add up to 11. For [1, 2, 3, 5] the total is 11, which is odd, so no split is possible. For [1, 2, 5] the total is 8, so each group would need 4, but the numbers can only make 1, 2, 3, 5, 6, 7 and 8, never 4, so the answer is false.
The statement asks for O(n * sum) time and O(sum) extra space, where n is the number of values and sum is their total.
Approach: which sums can the numbers make?
If the total is odd, the answer is false, since two equal halves always add up to an even number. Otherwise let half be the total divided by 2. If some of the numbers add up to exactly half, the rest make the other half, so the question becomes: can some of the numbers add up to half?
Trying every possible group is far too slow, since 200 numbers can be grouped in 2^200 ways. Instead, keep a table of booleans: can[s] says whether some of the numbers seen so far add up to s, for every s from 0 to half. Before any number is seen only can[0] is true: no numbers at all make 0.
Then add the numbers one at a time. For a number num, every sum that could be made before gives a new sum with num added, so can[s] becomes true when can[s - num] was already true. For [1, 5, 11, 5] the sums that can be made grow like this (half is 11):
| After | Sums that can be made |
|---|---|
| no numbers | 0 |
| 1 | 0, 1 |
| 5 | 0, 1, 5, 6 |
| 11 | 0, 1, 5, 6, 11 |
| 5 | 0, 1, 5, 6, 10, 11 |
The table contains 11 at the end, so the answer is true. For [1, 2, 5], whose half is 4, the sums are 0, 1, 2 and 3 after the numbers 1 and 2, and still 0, 1, 2 and 3 after the 5, which is too big to matter. 4 is never reached, and the answer is false.
The order of the inner loop matters. The sums are visited from half down to num. Going down, can[s - num] still holds its value from before this number, so each number is used at most once. Going up, can[s - num] may already include num itself, and the number would be reused. On [1, 2, 5] an upward loop makes 4 as 1 + 1 + 1 + 1 and wrongly answers true.
Step by step
- Add everything up.
accumulate(nums.begin(), nums.end(), 0)adds every number to the starting value 0 and stores the result intotal. - Return
falsefor an odd total, checked withtotal % 2 == 1. - Compute
halfastotal / 2. The target is now to make exactly this sum from some of the numbers. - Create the table.
vector<bool> can(half + 1, false)has one entry for each sum from 0 tohalf, all false. The constructor takes the size first and the value for every element second. - Set
can[0]totrue. The empty group makes 0, and every other sum grows from it. - Loop over the numbers with a range-based
for. After the loop has handled a number, the table knows every sum the numbers so far can make, each used at most once. - Loop over the sums downward, with
sfromhalfwhiles >= num. A sum smaller thannumcan't contain it. - Update the entry:
can[s] = can[s] || can[s - num]. Either the sum was already possible, or it is possible by addingnumto a smaller sum that was. - Return
can[half], after the outer loop.
The solution in C++
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2 == 1) {
return false;
}
int half = total / 2;
vector<bool> can(half + 1, false);
can[0] = true;
for (int num : nums) {
for (int s = half; s >= num; s--) {
can[s] = can[s] || can[s - num];
}
}
return can[half];
}
};
The C++ details worth a closer look:
accumulateand its starting value. The third argument,0, is anint, so the sum is computed as anint. That is safe here: at most 200 numbers of at most 100 give 20,000.vector<bool>. It is a space-saving special case ofvectorthat stores one bit per element. For this use it reads and writes like any other vector.||short-circuits. Ifcan[s]is already true, the right side isn't evaluated. Either way the result is the same.- The loop condition
s >= num. It keepss - numfrom going below 0, so the index is always valid. The variables areint, so the countdown is safe, unlike a loop with an unsigned counter. numsis a non-const reference, which the lesson's signature requires. The method only reads it.
Complexity
Time: O(n * sum). Each of the n numbers walks over at most half + 1 sums, with a constant amount of work for each.
Space: O(sum). The table holds half + 1 booleans. Reusing a single row of the table, instead of a new row for each number, is what keeps the space this small, and it only works because the sums are visited downward.
Edge cases and common mistakes
- Looping upward. Reusing a number: the answer for
[1, 2, 5]flips fromfalsetotrue. - Skipping the odd-total check. Integer division makes
total / 2round down, so an odd total would be tested against a wrong target. Without the check,[1, 2, 3, 5](total 11, half 5) answerstruebecause 2 + 3 = 5, and[1]answerstruebecause its half is 0. - A single number.
[1]has an odd total and givesfalse. The input always has at least one number, but one number can never be split into two equal groups. - Two equal numbers.
[1, 1]and[2, 2]givetrue: each copy goes into its own group. - Forgetting
can[0] = true. Then every entry stays false forever, since every sum is built from smaller ones that started at 0. - A large number. If a number is bigger than
half, the inner loop doesn't run for it, and that number can't be in the group that makeshalf. It is part of the other group. For[1, 5, 11, 5], the 11 equalshalf, so it makes the sum 11 alone. - Largest input. 200 numbers equal to 100 give a total of 20,000 and a table of 10,001 entries. The answer is
true.
Testing
[1, 5, 11, 5]givestrue.[1, 2, 3, 5]givesfalse.[1, 2, 5]givesfalse.[1]givesfalse.[3, 3, 3, 3]givestrue.[2, 3, 4, 5, 6]givestrue: the total is 20, and 4 + 6 = 10.[1, 2, 3, 4, 5, 6, 7]givestrue.
