nums walked from the right, as the code does
dp as a row cell t is T when some subset of the numbers seen so far sums to t · sums above target are left out
public boolean canPartition(int[] nums) { int sum = 0; for (int x : nums) { sum += x; } if (sum % 2 != 0) { return false; } Set<Integer> dp = new HashSet<>(); dp.add(0); int target = sum / 2; for (int i = nums.length - 1; i >= 0; i--) { Set<Integer> nextDP = new HashSet<>(); for (int t : dp) { if (t + nums[i] == target) { return true; } nextDP.add(t + nums[i]); nextDP.add(t); } dp = nextDP; } return false;}
- target
- —
- i, nums[i]
- —
- dp.size()
- —
- dp (sorted)
- —
Why it works
- Brute force tries every subset: 2ⁿ ways to choose one group, each summed: exponential.
- Only the target matters: two equal groups each total
sum / 2, so the question becomes "does some subset sum totarget?". An odd total answersfalseat once. - Grow the set of reachable sums: before any number, only 0 is reachable. Each new number
xkeeps every old sum (skipx) and adds every old sum plusx(take it). The arcs show that shift byx. - Cost: the set never holds more than
sum + 1values, and each number touches each once: O(n · sum) time, O(sum) space. That is pseudo-polynomial: fine for small totals, slow for huge ones. - Pitfall: adding into the set you are looping over reuses a number twice (and a
HashSetthrowsConcurrentModificationException). That is why the code buildsnextDP. With a boolean array, looptdownward for the same reason. - Related: this is 0/1 knapsack on sums. Target Sum and Last Stone Weight II reduce to the same reachable-sums idea.