• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100
• Every element must land in exactly one of the two groups
• The groups do not need to be the same size, only the same sum

"Split into two equal halves" sounds like it needs two decisions per element — which group does it go in? It does not. Watch.

Let total be the sum of everything. If the two groups are to be equal, each must sum to total / 2. And here is the collapse: once you have chosen one group, the other group is whatever is left over, and its sum is forced. So you never need to think about the second group at all. The question becomes:

Is there some subset of nums whose sum is exactly total / 2?

That reduction buys us two things immediately. First, an instant rejection: if total is odd, there is no such thing as half of it in whole numbers, and the answer is false before we do anything. On [1, 2, 3, 5] the total is 11, so no split can exist — done in one line. Second, it turns a vague partitioning question into a crisp target-hitting question, and target-hitting questions have a standard shape.

Call the target T = total / 2.

Every element is either in the chosen subset or not. With n elements that is 2ⁿ possible subsets, and we could sum each one and check it against T. For n = 200 that is a number with sixty digits. Not viable, but it is the correct starting point, because it names the decision: for each element, take it or leave it.

I go through the elements one at a time, from the last toward the first. Standing at element i with a target t still to reach, I have two choices:

I only need one of the two to work, so I join them with or. The two things I must track are which element I'm on (i) and how much target is left (t).

f(i, t) = f(i-1, t) or ( t >= nums[i] and f(i-1, t - nums[i]) )

(This is the yes/no flavour: a counting version would use +, a best-value version max.)

Base cases, two of them:

We start the whole thing by asking about the last element with the full target: f(n-1, T).

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0: return False
    T = total // 2
    n = len(nums)
    memo = {}

    def f(i, t):
        if t == 0: return True
        if i == 0: return nums[0] == t
        if (i, t) in memo: return memo[(i, t)]
        skip = f(i - 1, t)
        take = t >= nums[i] and f(i - 1, t - nums[i])
        memo[(i, t)] = take or skip
        return memo[(i, t)]

    return f(n - 1, T)

How fast is this now? Each state (i, t) is worked out once and then read back from the notebook. There are n choices for i and T+1 choices for t, so at most n × (T+1) states in all. With n ≤ 200 and T ≤ 10000, that is about two million small steps — fast.

The rule to remember: a memoised solution's speed is simply how many different states there are, because each state is solved only once.

Turn the recursion into a table the same mechanical way. Let dp[i][t] hold exactly what f(i, t) returned: true if we can make the sum t using elements from index 0 through i.

Now read the recurrence as an assignment. It said

f(i, t) = f(i-1, t) or ( t >= nums[i] and f(i-1, t - nums[i]) )

so, swapping each call for an array read, the very same line becomes

dp[i][t] = dp[i-1][t] or ( t >= nums[i] and dp[i-1][t - nums[i]] )

It is the identical formula. We just store each answer in a cell instead of returning it.

Fill the rows top to bottom (i = 0, 1, 2, ...), so each row i-1 is ready before row i uses it.

The base cases just get copied over from the recursion. Read each base line and write down the cell it describes:

Then the loop starts at row i = 1, and the answer is dp[n-1][T]:

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0: return False
    T = total // 2
    n = len(nums)

    # dp[i][t] = can we make t using elements from index 0 through i?
    dp = [[False] * (T + 1) for _ in range(n)]
    for i in range(n):
        dp[i][0] = True                 # target 0: take nothing
    if nums[0] <= T:
        dp[0][nums[0]] = True           # first element alone can only make its own value

    for i in range(1, n):
        for t in range(1, T + 1):
            skip = dp[i - 1][t]
            take = dp[i - 1][t - nums[i]] if t >= nums[i] else False
            dp[i][t] = take or skip

    return dp[n - 1][T]

Row i reads only from row i-1, the elements before it. Nothing further back is ever consulted. So one row is enough — as long as we are careful about the order we overwrite it in.

Here is the trap. If we keep one array dp and sweep t upward, then when we compute dp[t] we read dp[t - nums[i]], which is a smaller index — and on this sweep we have already overwritten it with the new row's value. That means we would use element i once and then immediately use it again. That is a different problem, where each element may be used any number of times. To keep each element usable once, sweep t downward, so every value we read still comes from the previous row:

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0: return False
    T = total // 2

    dp = [False] * (T + 1)
    dp[0] = True                       # zero is always makeable

    for num in nums:
        for t in range(T, num - 1, -1):     # downward! see the note
            dp[t] = dp[t] or dp[t - num]

    return dp[T]

dp[11] is true, so the answer is true — the subset {11} sums to 11 and the leftovers {1, 5, 5} also sum to 11.

Now the failing case [1, 2, 3, 5]: total 11 is odd, and we return false on the very first line without building anything.

And a case that survives the parity check but still fails, [1, 1, 3]: total 5 is odd — also rejected early. Try [2, 2, 3, 5]: total 12, T = 6, reachable sums are {0, 2, 3, 4, 5, 7, ...}; 6 never appears, so false. Even sums are not enough on their own.

Two ideas travel far beyond this problem.

The first is the reduction: a question about splitting into groups became a question about hitting one number, because fixing one group fixes the other. Whenever a problem asks you to divide things up, check whether one side determines the other — it very often does, and it halves the thinking.

The second is the subset-sum skeleton itself: walk the items, and at each one decide take-or-skip while carrying "how much budget is left" in the state. Swap the combining operation and the same skeleton answers a whole family of questions: or for "is it possible", + for "how many ways", max for "best value within budget". And the descending inner loop is what the "each item once" rule looks like in code: every item is taken zero times or one time, never more.