In a 0/1 knapsack problem you choose items, and each item is either taken once or left out. The state is a sum w. In can_partition, dp[w] is True when some of the items processed so far add up to exactly w.

Processing items in order is what makes the table correct. After item k, dp describes only the first k items. The next item x adds one choice: take x once, so dp[w] also becomes True when dp[w - x] was True before x.

At the start, only the sum 0 is reachable, by choosing no item. So dp[0] is True and every other cell is False. If every cell started True, every target would look reachable.

Example: for nums = [1, 5, 11, 5] the target is 11. The reachable sums are [0, 1] after the first item, [0, 1, 5, 6] after the second, [0, 1, 5, 6, 11] after 11, and [0, 1, 5, 6, 10, 11] after the last 5. The target 11 is reachable, so the answer is True.

Think of a table with one row per item, where dp[i][w] = dp[i - 1][w] or dp[i - 1][w - x]. Both terms read row i - 1. The code compresses the table to one array, so dp[w - x] must still hold the value from before item x.

Looping w downward gives exactly that. When the loop updates dp[w], the smaller index w - x has not changed yet in this pass. So x is used at most once.

Looping w upward does the opposite. dp[w - x] was already updated in this pass, so it may already include x, and dp[w] uses x a second time.

Example: can_partition([2, 6]) has total 8 and target 4, and the answer is False. If the loop runs upward, dp[2] becomes True, then dp[4] reads dp[2] and becomes True. The single 2 was used twice. The downward loop returns False.

Two equal halves need an even total. The code checks total % 2 != 0 first and returns False.

Without the check, total // 2 rounds down. For nums = [1, 2] the total is 3, and the rounded target is 1. The subset [1] reaches 1, so the code would return True for a split that does not exist.

The same idea turns other problems into this one. In Last Stone Weight II (LC 1049), splitting the stones into two groups with the smallest weight difference means finding the largest reachable sum that is at most half of the total. For [2, 7, 4, 1, 8, 1] the answer is 1. In Target Sum (LC 494), choosing plus or minus signs turns into counting the subsets that add up to (total + target) / 2. The table then holds counts, and dp[0] starts at 1.

There are N items and target sums, and each update is one comparison. The time is O(N * Target). The space is O(Target) for the single array.

The cost depends on the value of target, not on how many digits it has. A target of 10^9 would need a billion-entry array. This is called pseudo-polynomial time: it is polynomial in the number's value but exponential in the number of bits that write it. So check the constraints first. In Partition Equal Subset Sum (LC 416), the total is at most 20,000.

A second limit can be a pair. In Ones and Zeroes (LC 474), each string uses some zeros and some ones, and two budgets limit the choice. The state becomes the pair (zeros, ones), and both loops run downward. The time is O(N * M * K) for M zeros and K ones. For ["10", "0001", "111001", "1", "0"] with 5 zeros and 3 ones, the answer is 4.