Free Backtracking lessonsBacktracking · Stage 1 · Combinations · Step 2

Combination sum, each number once

Reuse the forward-only walk from combine, but stop on a running total instead of a fixed size. About 9 minutes.

Same walk, a different stopping rule

This is the same forward-only walk as before: a starting point, a loop over later numbers, choose, recurse, unchoose. Only the base case changes. Instead of stopping at a certain size, you stop when the numbers you have picked add up to exactly the target.

Think of paying a bill from a pile of coins: keep track of how much is still left to pay, and stop when it hits zero.

Track what is left: it starts at the target and shrinks by each pick.

Base case: nothing left and something picked, so save a copy and return.

nums = [2, 3, 6, 7], target = 9 · the tag is what's left to reach

Pick 2: 7 left. Later numbers only.

Move 1 of 6

Break, don't just skip

The numbers arrive sorted, and all are positive. So inside the loop, the moment you meet a number bigger than what is left, every number after it is bigger still, and none can fit.

Stop the whole loop right there instead of checking each remaining number. It is like walking down a sorted price list: once one item is too expensive, all the rest are too.

Break, not continue: a number that is too big ends the whole loop, not just that round.

Needs sorted input: the break is safe only because later numbers are bigger.

In code

res = []
def go(start, left, curr):
    if left == 0 and curr:
        res.append(list(curr))
        return
    for i in range(start, len(nums)):
        x = nums[i]
        if x > left:
            break
        curr.append(x)
        go(i + 1, left - x, curr)
        curr.pop()
go(0, target, [])
return res

Quick check

Why can the loop break (instead of continue) as soon as nums[i] > remaining?

Anums is sorted ascending and every value is positive, so every number after nums[i] is too big as well
Bbreak is always safe here, whether or not nums happens to be sorted
Cbreak and continue would find the same combinations either way; break is just tidier

Show the answer

nums is sorted ascending and every value is positive, so every number after nums[i] is too big as well. Once one number in a sorted, all-positive array is too big, every later number is at least as big, so none of them can work either.

Your problem

Combination sum, each number once

Given an array nums of distinct positive integers sorted in increasing order, and an integer target, return every combination of one or more numbers from nums — each used at most once — whose values sum to exactly target. List the numbers within each combination in increasing order, and list the combinations themselves in lexicographic order.

Example

nums = [2, 3, 6, 7], target = 9 → [[2, 7], [3, 6]]

1 ≤ nums.length ≤ 10 · 1 ≤ nums[i] ≤ 30 · nums is sorted in strictly increasing order · 1 ≤ target ≤ 100

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.