AI Hints
Home›DSA in Python Tutorial›Backtracking
DSA in Python · Lesson 99 of 132

Practice: Combination Sum

Hitting a target.

⏱ 2 min read▶ Video at 1:58:33🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Using coins of two, three, and five, find every combination that adds up to eight. You can use a coin more than once. Pause. When should you stop exploring a branch early?

Practice: Combination Sum
From the video: Practice: Combination Sum
  • Coins 2, 3, 5
  • Every way to make 8
  • When to stop early?

Pruning dead ends

We keep the remaining amount. If it hits zero, we've found a combination. If a coin is bigger than what remains, there's no point trying it, or anything bigger, so we stop. That's pruning, and it saves huge amounts of work. Starting each loop at the current coin avoids repeating the same combination in a different order. Run it. Three combinations make eight.

combo.pypython
def combo_sum(coins, target):
    coins, results = sorted(coins), []
    def explore(start, remaining, path):
        if remaining == 0:
            results.append(path)
            return
        for i in range(start, len(coins)):
            if coins[i] > remaining:
                break
            explore(i, remaining - coins[i], path + [coins[i]])
    explore(0, target, [])
    return results

print(combo_sum([2, 3, 5], 8))
Output
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Pruning

Pruning means cutting off branches that can't possibly lead to an answer. Sorting first makes it easy, because once one coin is too big, all the later ones are too. Good pruning can turn a backtracking search that takes hours into one that takes milliseconds.

keyvalue
Foundremaining == 0
Prunecoin > remaining
Sort firstso you can stop early
start indexno duplicate orders

Summary

Combination sum explores choices, but prunes any branch that overshoots the target. Next, the most famous backtracking puzzle. Eight queens.

Key takeaways
  • Track the remainder
  • Prune when too big
  • Start from the current coin
Next up: Practice: N Queens — no two queens attack