Can a subset hit this total

A family of problems that look different and are one table: can some subset of these numbers reach a target.

The table

def subset_sum(nums, target):
    reachable = [False] * (target + 1)
    reachable[0] = True                       # the empty subset
    for n in nums:
        for t in range(target, n - 1, -1):    # downward: each number once
            reachable[t] |= reachable[t - n]
    return reachable[target]

reachable[t] means some subset sums to exactly t. It is knapsack with a boolean instead of a value, and the same take or skip structure.

The loop direction again

Iterating t downward means reachable[t - n] still holds the previous number's state, so n is used at most once.

Iterate upward and reachable[t - n] may already include n, so it gets used repeatedly, and the function now answers a different question: can these numbers, with repetition, reach the target. That is the coin change problem.

One loop direction, two problems. This is the same lesson as the knapsack capacity loop, and it is worth meeting twice because it is the most common silent bug in the subject.

Partition into two equal halves

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False                  # odd total, impossible
    return subset_sum(nums, total // 2)

Finding a subset summing to half is finding the partition, because the rest is the other half. The odd check first is worth keeping: it is a one line answer for a case the table would spend real time on.

Minimum difference partition

The same table, read differently. Fill it for every total up to half the sum, then take the largest reachable one:

for t in range(total // 2, -1, -1):
    if reachable[t]:
        return total - 2 * t          # the gap between the two halves

The complexity, honestly

O(n x target), which is pseudo-polynomial: polynomial in the value of the target, not in the number of bits used to write it. Doubling the target doubles the work, so a target of ten million is slow with only twenty numbers.

Subset sum is NP-complete. This table is not a polynomial algorithm for it, and saying so correctly is a thing interviewers listen for.