Combination Sum IV
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
Count the ordered sequences of numbers (reuse allowed) that add up to the target; different orders count separately.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many sequences add to 0? (the empty one)
- Hint 2For a total, consider each number as the LAST element.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Climbing a staircase of 4 stairs where you may take 1, 2 or 3 stairs at a time. 1+2 and 2+1 are different climbs. For each stair count, the number of ways is the sum of the ways for (count - 1), (count - 2), (count - 3) because the last step was one of those.
- The obvious way
Recursion enumerating sequences repeats work: exponential.
- The key insight
ways[0] = 1. For each total from 1 up to target and each number not above it: ways[total] += ways[total - number]. Order matters because the outer loop is the total, not the number.
- The algorithm
- ways[0] = 1.
- For each total 1..target: loop over the numbers.
- If number <= total: add ways[total - number].
- Return ways[target].
Watch it run
Examplenums = [1, 2, 3], target = 4
Total 0: 1 way (empty). Total 1: 1 way (1).
ways: 1, 1
Where people slip
- Swapping the loops (numbers outside) counts combinations, not ordered sequences.
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_sum4(nums, target):
ways = [1] + [0] * target # ways[0] = 1: the empty sequence
for total in range(1, target + 1):
for number in nums:
if number <= total:
ways[total] += ways[total - number] # the last step was this number
return ways[target]Now 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.