Each item once

The unit's last shape, and the one that most often hides behind a question about something else.

Why it works

Reachable totals, using each item at most once

The state is a total and the answer is whether it is reachable. That looks identical to the coin problem, and the difference is that each item may be used only once, which the coin loop does not enforce.

The cleanest way to handle it is to process one item at a time and, for each, update which totals become reachable by adding it. Since each item is considered in exactly one pass, it cannot be reused.

1values = [1, 5, 11, 5]2target = sum(values) // 23 4reachable = {0}5for value in values:6    reachable |= {existing + value for existing in reachable7                  if existing + value <= target}8    print("after", value, "->", sorted(reachable))

The target here is 11, and it first becomes reachable on the third pass.

Why it works

Why the set version cannot double-use

The comprehension reads reachable as it was at the start of the statement and unions the result afterward, so a value added in this pass cannot be extended again in the same pass.

The array version has the same requirement and enforces it differently: iterate the totals downward, so a cell updated in this pass is never read again during it. That is the opposite direction from the unlimited-reuse version in the earlier lesson, and the direction is precisely what encodes once versus many times.

Two loops that differ only in direction and mean entirely different problems is worth pausing on. If a subset-sum solution allows reusing an item, check the loop direction first.

1def reachable_totals(values, target):2    """Array version. The downward loop is what forbids reuse."""3    reachable = [False] * (target + 1)4    reachable[0] = True5    for value in values:6        for total in range(target, value - 1, -1):        # downward7            if reachable[total - value]:8                reachable[total] = True9    return reachable10 11print(reachable_totals([1, 5, 11, 5], 11)[11])12print(reachable_totals([3], 6)[6])

Predict the output· 5 min

Predict the output: which loop direction reuses an item

One item of size 3 is offered to a table of reachable totals, once upward and once downward. Type the two lines it prints.

Python

1size = 32target = 93 4upward = [True] + [False] * target5for total in range(size, target + 1):6    if upward[total - size]:7        upward[total] = True8 9downward = [True] + [False] * target10for total in range(target, size - 1, -1):11    if downward[total - size]:12        downward[total] = True13 14print("upward: ", [t for t, ok in enumerate(upward) if ok])15print("downward:", [t for t, ok in enumerate(downward) if ok])

Printed output

Problem· 32 min

Partition Equal Subset Sum

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def reachable_totals(values, target):2 """Array version. The downward loop is what forbids reuse."""3 reachable = [False] * (target + 1)4 reachable[0] = True5 for value in values:6 for total in range(target, value - 1, -1): # downward7 if reachable[total - value]:8 reachable[total] = True9 return reachable10 11print(reachable_totals([1, 5, 11, 5], 11)[11])12print(reachable_totals([3], 6)[6])

1size = 32target = 93 4upward = [True] + [False] * target5for total in range(size, target + 1):6 if upward[total - size]:7 upward[total] = True8 9downward = [True] + [False] * target10for total in range(target, size - 1, -1):11 if downward[total - size]:12 downward[total] = True13 14print("upward: ", [t for t, ok in enumerate(upward) if ok])15print("downward:", [t for t, ok in enumerate(downward) if ok])