Combination Sum
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given distinct positive numbers and a target, return all unique combinations that add up to the target. A number can be reused any number of times.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If order does not matter, how can you force a single order, such as ascending?
- Hint 2After choosing a coin you may choose the same coin again or a later one.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Paying an exact amount at a shop with coins of values 2, 3, 6, 7, using any coin as many times as you like. To avoid listing 2+2+3 and 3+2+2 as different, you always hand over coins from smallest to largest: once you move past a coin, you never go back to it. After each coin check what is left to pay: zero means done; if the next coin is bigger than what is left, stop.
- The obvious way
Try all multisets of coins and filter by sum: far too many.
- The key insight
Sort the numbers. Recurse with (start position, remaining amount). If remaining is 0, save a copy of the chosen coins. Otherwise try each coin from start onward: stop when a coin is bigger than the remaining; pick it, recurse with the SAME start (reuse allowed), then remove it.
- The algorithm
- Sort the candidates.
- remaining == 0: save a copy of the chosen coins.
- For each coin from start onward: stop if it is bigger than remaining.
- Choose it, recurse from the same coin, un-choose it.
Watch it run
Examplecandidates = [2, 3, 6, 7], target = 7
Pay with 2, 2, 2: 1 left to pay, but no coin is that small. Dead end, take a 2 back.
chosen: 2, 2
Where people slip
- Recurse with the same position (reuse) not position + 1.
- Starting the loop from 0 each time lists the same combination in different orders.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def combination_sum(candidates, target):
candidates.sort()
result = []
chosen = []
def pay(start, remaining):
if remaining == 0:
result.append(list(chosen)) # exact amount paid
return
for position in range(start, len(candidates)):
coin = candidates[position]
if coin > remaining:
break # this and all bigger coins are too big
chosen.append(coin)
pay(position, remaining - coin) # the same coin may be used again
chosen.pop() # backtrack
pay(0, target)
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.