Problem overview
The method canPartition receives nums, an array of positive integers, and returns true when the numbers can be split into two groups with equal sums, and false otherwise. Every number goes into exactly one group. Repeated values are separate numbers, and 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] it is false, because the total is 11, an odd number that can't be split into two equal halves. For [1, 2, 5] it is also false: the total is 8, so each group would have to reach 4, but the numbers can only make 1, 2, 3, 5, 6, 7 and 8. The array has up to 200 numbers, each from 1 to 100.
The algorithm should run in O(n · sum) time and use O(sum) space, where n is the number of values and sum their total.
Approach: can some numbers make exactly half?
If the total is odd, the answer is false at once. Otherwise let half be the total divided by 2. If some of the numbers add up to exactly half, the rest add up to the other half. So the question becomes: can a selection of the numbers, each used at most once, make 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, because no numbers at all make 0.
Then add the numbers one at a time. A new number num turns every sum that could be made before into a new sum with num added. So can[s] becomes true when can[s - num] was true. This is dynamic programming: each answer is built from the answers for smaller sums.
For [1, 5, 11, 5] the reachable sums, after each number, are:
after 1: 0, 1
after 5: 0, 1, 5, 6
after 11: 0, 1, 5, 6, 11
after 5: 0, 1, 5, 6, 10, 11
The half is 11, and it is reachable, so the answer is true.
Why the sums go down
The inner loop goes from half down to num. Going down, can[s - num] has not been touched yet for this number, so it still describes the numbers before it, and num is used at most once. Going up would let can[s - num] already include num, which lets a number be used again and again. With the loop going up, [1, 2, 5] would reach 4 as 1 + 1 + 1 + 1 and return true, while the correct answer is false.
Step by step
- Add up the numbers into
totalwithnums.reduce((sum, num) => sum + num, 0). It starts from 0 and adds each number to the running sum. - Reject an odd total: if
total % 2 === 1, returnfalse. Two equal halves always add up to an even number. - Compute
halfastotal / 2. The total is even here, so nothing is lost in the division. - Create
can,half + 1values, allfalse, withnew Array(half + 1).fill(false). - Set
can[0]totrue. Every sum grows from the empty selection. - Loop over the numbers with
for...of. - Loop over the sums with
let s = halfwhiles >= num, going down. A sum smaller thannumcan't contain it. - Update:
can[s] = can[s] || can[s - num]. The sumsis reachable if it already was, or ifs - numwas reachable before this number. - Return
can[half].
The solution in TypeScript
class Solution {
canPartition(nums: number[]): boolean {
const total: number = nums.reduce((sum, num) => sum + num, 0);
if (total % 2 === 1) {
return false;
}
const half: number = total / 2;
const can: boolean[] = new Array(half + 1).fill(false);
can[0] = true;
for (const num of nums) {
for (let s = half; s >= num; s--) {
can[s] = can[s] || can[s - num];
}
}
return can[half];
}
}
TypeScript details:
reducewith an initial value. The0is the starting sum. The result is anumber, and for an array with one element, such as[7], it gives 7.- Numbers are doubles.
total / 2is exact whentotalis even, andtotal % 2is 0 or 1 for positive totals. The values here are far below 2^53, so nothing loses precision. new Array(n).fill(false).new Array(half + 1)makes an array with that many empty slots, andfill(false)sets each one tofalse. The annotationboolean[]is only for the compiler.||short-circuits. Ifcan[s]is already true, the right side is not evaluated.- The loop variable.
sis declared withletbecause it counts down.numis aconstthat gets a new value on every pass offor...of.
Complexity
Time: O(n · sum). Each of the n numbers goes over at most half + 1 sums, with a constant amount of work for each. The largest input, 200 numbers of 100, has a half of 10,000 and finishes with about two million updates.
Space: O(sum). The table can holds half + 1 booleans.
Edge cases and common mistakes
- Odd total.
[1, 2, 3, 5]and[1]returnfalsebefore the table is even built. - Two equal numbers.
[2, 2]and[1, 1]returntrue, one number per group. - One number.
[100]returnsfalse: the total is even, but a single number can't fill two groups. A number larger thanhalfnever enters the inner loop, becauses >= numis false from the start. - Even total, no split.
[1, 2, 5]has total 8 and returnsfalse, and so does[2, 2, 3, 5]with total 12. An even total is necessary, not sufficient. - A split exists.
[3, 3, 3, 4, 5]and[1, 2, 3, 4, 5, 6, 7]both returntrue. - Looping up instead of down. It reuses numbers, as shown above for
[1, 2, 5]. - Table of the wrong size.
can[half]needshalf + 1entries, because indexes run from 0 tohalf. - Forgetting
can[0] = true. Without it, nothing ever becomes true, and the answer is alwaysfalse. - Largest input. 200 numbers equal to 100 return
true(100 per group). Changing one of them to 99 makes the total odd, and the answer isfalseat once.
Testing
[1, 5, 11, 5]givestrue.[1, 2, 3, 5]givesfalse.[1, 2, 5]givesfalse.[2, 2]givestrue.[1]givesfalse.[100]givesfalse.[3, 3, 3, 4, 5]givestrue.[2, 2, 3, 5]givesfalse.[1, 2, 3, 4, 5, 6, 7]givestrue.
