Builds on Subsets, which you haven’t finished yet.
Combinations / Combination Sum
start and the search tracks a remaining target, so it stops a branch when the remainder goes below zero.Combinations (LC 77)(opens leetcode.com)
What a combination is (assume nothing): a combination is a group of numbers where only which numbers are in the group matters, not their order. [1, 3] and [3, 1] are the same combination.
You get two integers n and k. Using the numbers 1 to n, list every group of exactly k different numbers. Each group appears once, and the groups can be returned in any order.
Combinations
target remainder ➔ candidates[start:] ➔ prune when candidate > remain| 1 | from typing import Callable, List, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def combinations(options: List[Item], is_complete: Callable[[List[Item]], bool], can_add: Callable[[List[Item], Item], bool], next_start: Callable[[int], int]) -> List[List[Item]]: |
| 7 | """Combinations: every group of options, each built once in index order. |
| 8 | is_complete(path) says when to save path. can_add(path, option) prunes an option. |
| 9 | next_start(i) is i + 1 when an option may be used once, and i when it may be reused. |
| 10 | Precondition: every branch ends, because can_add fails or is_complete holds. |
| 11 | B = the calls to backtrack. I = the loop steps over all calls. G = the groups saved. L = the longest group. |
| 12 | T = the cost of one can_add, is_complete or next_start call. |
| 13 | Time: O((B + I) * T + G * L) | Space: O(L) path + recursion stack, output not counted |
| 14 | """ |
| 15 | results: List[List[Item]] = [] |
| 16 | path: List[Item] = [] |
| 17 | |
| 18 | def backtrack(start: int) -> None: |
| 19 | # 1. Save a Complete Group: |
| 20 | # is_complete decides when path is a finished group (a target size or sum |
| 21 | # reached); stop there, since a shorter path is not yet an answer. |
| 22 | if is_complete(path): |
| 23 | results.append(list(path)) |
| 24 | return |
| 25 | |
| 26 | for i in range(start, len(options)): |
| 27 | # 2. Choose, Explore, Un-choose, Forward Only: |
| 28 | # can_add prunes an option that cannot help; next_start(i) is i + 1 when an |
| 29 | # option is used once and i when it may repeat, so each group is still built |
| 30 | # once, in index order, never both [1, 2] and [2, 1]. |
| 31 | if can_add(path, options[i]): |
| 32 | path.append(options[i]) |
| 33 | backtrack(next_start(i)) |
| 34 | path.pop() |
| 35 | |
| 36 | backtrack(0) |
| 37 | return results |
path is in increasing order and every number still allowed is at least start, so each group is built in exactly one order.Pick numbers only from start onward and recurse with backtrack(i + 1), so every group is built in increasing order. A group of numbers has exactly one increasing order, so the forward-only loop builds each combination once and never both [1, 2] and [2, 1]; save it when len(path) == k. The trap is the recursive call: pass i + 1, not start + 1, or the next pick can be smaller than the one just made.
See it run
Combinations, step by step
start 1path []saved 0
The top row holds the numbers 1 to n. The middle row is 1 when the number is in path. The bottom row is path, filled from the left.
ithe number the loop is looking atstartthe smallest number this call may usei = startthe loop number is the smallest allowed numberpaththe slot just added to pathundothe slot just removed from path
n = 4, k = 2, and path is empty, so need = 2. The loop in backtrack(1) stops at i = 3, because a later i leaves too few numbers.
Gotcha 1 of 4
- The trap
Gotcha 1: Recursing with
backtrack(start + 1)instead ofbacktrack(i + 1)Mistakebacktrack(start + 1)Fixbacktrack(i + 1)What happens: The next number must come after
i, the number just added.backtrack(start + 1)starts the next level afterstartinstead. Wheni > start, the next pick can beiagain or a smaller number. So groups such as[2, 2]appear.Example: n = 3, k = 2Mistake: returns [[1, 2], [1, 3], [2, 2], [2, 3]]Fix: returns [[1, 2], [1, 3], [2, 3]]
- Order matters, as in Permutations (LC 46):
[1, 2]and[2, 1]are two different answers. See Permutations - Only the number of ways is asked, as in Coin Change II (LC 518), not the combinations themselves, and there can be far too many to list. See Unbounded Knapsack
Deep Dive
What this card adds to Subsets: a target and a bound
The Subsets card already shows why a forward-only loop builds each group once. This card uses the same loop for groups that must reach a target, such as a length k or a sum.
It adds two things. First, is_complete decides when to save, so path is saved only when it is finished and the branch stops there. Second, can_add and the loop bound cut a branch that can never finish.
The orders [1, 2] and [2, 1] are one group. Only the increasing order is built, because the recursion goes to i + 1.
Why the recursion goes to i + 1, not start + 1
Take combine(4, 2). At the first call, the loop picks i = 1, then i = 2, then i = 3. After a pick of i, every later pick must be larger than i.
backtrack(i + 1) does this. At the pick i = 2, the call is backtrack(3). The next level then sees only 3 and 4.
backtrack(start + 1) is wrong. At the pick i = 2 with start = 1, it calls backtrack(2), and the next level can pick 2 again. For combine(3, 2), the result then includes [2, 2].
The result for combine(4, 2) is [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]. This is the example of Combinations (LC 77).
Why the loop ends at n - need + 1
need = k - len(path) is how many numbers are still missing. If you pick i, then n - i larger numbers are left. You need need - 1 more after i, so the pick is useful only when n - i >= need - 1. That gives i <= n - need + 1.
range stops before its end value, so the code writes range(start, n - need + 2). For combine(4, 2) at the first call, need = 2 and the loop is range(1, 4). The pick i = 4 is never tried, because no number would remain for the second position.
This bound is a saving, not a change of the answer. For combine(4, 2), backtrack runs 10 times with the bound and 11 times without it. For combine(10, 5), it runs 462 times with the bound and 638 times without it.
Variants: reuse, repeats and a sum target
The card's template changes in one place for each variant. next_start(i) is i + 1 when each number is used once. It is i when a number may be reused, as in Combination Sum (LC 39). The loop still starts at start, so [2, 3] and [3, 2] are not both built.
If the same value appears twice in the input, as in Combination Sum II (LC 40), sort first and skip candidates[i] when i > start and it equals candidates[i - 1]. This is the skip test from the Subsets card.
For a sum target, as in Combination Sum III (LC 216), can_add rejects a number larger than the remaining sum. If the candidates are sorted, the loop can break at the first rejected number, because every later number is larger.
The cost is O((B + I) * T + G * L). B is the number of backtrack calls and I is the number of loop steps. G is the number of saved groups and L is the longest group. For combine(n, k), the groups are C(n, k), and each copy costs O(k).
60-Second Pitch
"The order inside a group does not matter, so I build each group in increasing order only. The loop picks from start, and the recursion goes to i + 1. I save a copy of path when it has k numbers. Before that, I bound the loop with need = k - len(path), so a pick that leaves too few numbers is never tried. The time is proportional to the number of calls plus k times C(n, k) for the copies. The space is O(k). If a number may be reused, I recurse with i and keep the same loop start."
Common Questions
- Why does a combination use
i + 1and not restart the loop at 0? A group has one increasing order. With
i + 1, the next pick is always larger, so[1, 2]is built and[2, 1]is not. A loop from 0 builds both, and the same group is saved twice.- What is the time complexity of
combine(n, k)? The saved groups number C(n, k), and each copy costs
O(k), so the output takes O(k * C(n, k)). The loop bound keeps the extra calls small. The space isO(k)forpathand the recursion stack.- How do you allow a number to be used many times?
Recurse with
backtrack(i, ...)and notbacktrack(i + 1, ...). The loop still starts atstart. This is Combination Sum (LC 39). You also need a way to stop, such as a remaining sum that reaches 0 or becomes negative.- How do you handle repeated values in the input?
Sort the input. In each call, skip
candidates[i]wheni > startand it equalscandidates[i - 1]. This is Combination Sum II (LC 40). The test usesstartso that the first pick of each call is never skipped.- Why is the loop bound
n - need + 2and notn + 1? A pick
iis useful only if enough larger numbers remain to finish the group. The last usefuliisn - need + 1, andrangestops before its end, so the end isn - need + 2. The answer is the same withn + 1, but more calls run: 638 and not 462 forcombine(10, 5).
SWE Reasoning
Spot it
- The answer is a list of groups, and the order inside a group does not matter.
- Every group must reach a target: a length
k, a sum, or a count of items. - A number may be used once, or many times. The statement says which.
- A partial group that has passed the target can be cut at once, for example when the sum is already too large.
- The input has repeated values and the answer must not list a group twice. Sort and skip the repeat.
The invariant, step by step
backtrack(start)runs. Ifis_complete(path)is True, such aslen(path) == k, it saveslist(path)and returns.- The loop runs
ifromstart. Forcombine, it stops atn - need + 1, because a laterileaves too few numbers. path.append(i)makes the pick.backtrack(i + 1)explores every group that continues with larger numbers.path.pop()removes the pick, so the nextistarts from the samepath.pathis always in increasing order, and every number still allowed is at leaststart. A group has one increasing order, so each group is built once.
Traps
backtrack(start + 1)instead ofbacktrack(i + 1). The next pick can be a number that is already inpath.combine(3, 2)returns[[1, 2], [1, 3], [2, 2], [2, 3]].- A loop that restarts at 0 for reuse. For reuse, change the recursion to
backtrack(i, ...). The loop must still start atstart. A loop from 0 builds[2, 3]and[3, 2]for target 5. - The loop bound one too low.
range(start, n - need + 1)loses every group that ends inn. The end must ben - need + 2. - No skip for repeated values. In Combination Sum II (LC 40), the same number twice starts the same group twice. Sort, then skip when
i > startand the value equals the left neighbour. - Saving
pathand notlist(path). The saved lists change whenpathchanges.
Practice
Builds on Subsets, which you haven’t finished yet.
Combinations / Combination Sum
start and the search tracks a remaining target, so it stops a branch when the remainder goes below zero.Combinations (LC 77)(opens leetcode.com)
What a combination is (assume nothing): a combination is a group of numbers where only which numbers are in the group matters, not their order. [1, 3] and [3, 1] are the same combination.
You get two integers n and k. Using the numbers 1 to n, list every group of exactly k different numbers. Each group appears once, and the groups can be returned in any order.
Combinations
target remainder ➔ candidates[start:] ➔ prune when candidate > remain| 1 | from typing import Callable, List, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def combinations(options: List[Item], is_complete: Callable[[List[Item]], bool], can_add: Callable[[List[Item], Item], bool], next_start: Callable[[int], int]) -> List[List[Item]]: |
| 7 | """Combinations: every group of options, each built once in index order. |
| 8 | is_complete(path) says when to save path. can_add(path, option) prunes an option. |
| 9 | next_start(i) is i + 1 when an option may be used once, and i when it may be reused. |
| 10 | Precondition: every branch ends, because can_add fails or is_complete holds. |
| 11 | B = the calls to backtrack. I = the loop steps over all calls. G = the groups saved. L = the longest group. |
| 12 | T = the cost of one can_add, is_complete or next_start call. |
| 13 | Time: O((B + I) * T + G * L) | Space: O(L) path + recursion stack, output not counted |
| 14 | """ |
| 15 | results: List[List[Item]] = [] |
| 16 | path: List[Item] = [] |
| 17 | |
| 18 | def backtrack(start: int) -> None: |
| 19 | # 1. Save a Complete Group: |
| 20 | # is_complete decides when path is a finished group (a target size or sum |
| 21 | # reached); stop there, since a shorter path is not yet an answer. |
| 22 | if is_complete(path): |
| 23 | results.append(list(path)) |
| 24 | return |
| 25 | |
| 26 | for i in range(start, len(options)): |
| 27 | # 2. Choose, Explore, Un-choose, Forward Only: |
| 28 | # can_add prunes an option that cannot help; next_start(i) is i + 1 when an |
| 29 | # option is used once and i when it may repeat, so each group is still built |
| 30 | # once, in index order, never both [1, 2] and [2, 1]. |
| 31 | if can_add(path, options[i]): |
| 32 | path.append(options[i]) |
| 33 | backtrack(next_start(i)) |
| 34 | path.pop() |
| 35 | |
| 36 | backtrack(0) |
| 37 | return results |
path is in increasing order and every number still allowed is at least start, so each group is built in exactly one order.Pick numbers only from start onward and recurse with backtrack(i + 1), so every group is built in increasing order. A group of numbers has exactly one increasing order, so the forward-only loop builds each combination once and never both [1, 2] and [2, 1]; save it when len(path) == k. The trap is the recursive call: pass i + 1, not start + 1, or the next pick can be smaller than the one just made.
See it run
Combinations, step by step
start 1path []saved 0
The top row holds the numbers 1 to n. The middle row is 1 when the number is in path. The bottom row is path, filled from the left.
ithe number the loop is looking atstartthe smallest number this call may usei = startthe loop number is the smallest allowed numberpaththe slot just added to pathundothe slot just removed from path
n = 4, k = 2, and path is empty, so need = 2. The loop in backtrack(1) stops at i = 3, because a later i leaves too few numbers.
Gotcha 1 of 4
- The trap
Gotcha 1: Recursing with
backtrack(start + 1)instead ofbacktrack(i + 1)Mistakebacktrack(start + 1)Fixbacktrack(i + 1)What happens: The next number must come after
i, the number just added.backtrack(start + 1)starts the next level afterstartinstead. Wheni > start, the next pick can beiagain or a smaller number. So groups such as[2, 2]appear.Example: n = 3, k = 2Mistake: returns [[1, 2], [1, 3], [2, 2], [2, 3]]Fix: returns [[1, 2], [1, 3], [2, 3]]
- Order matters, as in Permutations (LC 46):
[1, 2]and[2, 1]are two different answers. See Permutations - Only the number of ways is asked, as in Coin Change II (LC 518), not the combinations themselves, and there can be far too many to list. See Unbounded Knapsack
Deep Dive
What this card adds to Subsets: a target and a bound
The Subsets card already shows why a forward-only loop builds each group once. This card uses the same loop for groups that must reach a target, such as a length k or a sum.
It adds two things. First, is_complete decides when to save, so path is saved only when it is finished and the branch stops there. Second, can_add and the loop bound cut a branch that can never finish.
The orders [1, 2] and [2, 1] are one group. Only the increasing order is built, because the recursion goes to i + 1.
Why the recursion goes to i + 1, not start + 1
Take combine(4, 2). At the first call, the loop picks i = 1, then i = 2, then i = 3. After a pick of i, every later pick must be larger than i.
backtrack(i + 1) does this. At the pick i = 2, the call is backtrack(3). The next level then sees only 3 and 4.
backtrack(start + 1) is wrong. At the pick i = 2 with start = 1, it calls backtrack(2), and the next level can pick 2 again. For combine(3, 2), the result then includes [2, 2].
The result for combine(4, 2) is [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]. This is the example of Combinations (LC 77).
Why the loop ends at n - need + 1
need = k - len(path) is how many numbers are still missing. If you pick i, then n - i larger numbers are left. You need need - 1 more after i, so the pick is useful only when n - i >= need - 1. That gives i <= n - need + 1.
range stops before its end value, so the code writes range(start, n - need + 2). For combine(4, 2) at the first call, need = 2 and the loop is range(1, 4). The pick i = 4 is never tried, because no number would remain for the second position.
This bound is a saving, not a change of the answer. For combine(4, 2), backtrack runs 10 times with the bound and 11 times without it. For combine(10, 5), it runs 462 times with the bound and 638 times without it.
Variants: reuse, repeats and a sum target
The card's template changes in one place for each variant. next_start(i) is i + 1 when each number is used once. It is i when a number may be reused, as in Combination Sum (LC 39). The loop still starts at start, so [2, 3] and [3, 2] are not both built.
If the same value appears twice in the input, as in Combination Sum II (LC 40), sort first and skip candidates[i] when i > start and it equals candidates[i - 1]. This is the skip test from the Subsets card.
For a sum target, as in Combination Sum III (LC 216), can_add rejects a number larger than the remaining sum. If the candidates are sorted, the loop can break at the first rejected number, because every later number is larger.
The cost is O((B + I) * T + G * L). B is the number of backtrack calls and I is the number of loop steps. G is the number of saved groups and L is the longest group. For combine(n, k), the groups are C(n, k), and each copy costs O(k).
60-Second Pitch
"The order inside a group does not matter, so I build each group in increasing order only. The loop picks from start, and the recursion goes to i + 1. I save a copy of path when it has k numbers. Before that, I bound the loop with need = k - len(path), so a pick that leaves too few numbers is never tried. The time is proportional to the number of calls plus k times C(n, k) for the copies. The space is O(k). If a number may be reused, I recurse with i and keep the same loop start."
Common Questions
- Why does a combination use
i + 1and not restart the loop at 0? A group has one increasing order. With
i + 1, the next pick is always larger, so[1, 2]is built and[2, 1]is not. A loop from 0 builds both, and the same group is saved twice.- What is the time complexity of
combine(n, k)? The saved groups number C(n, k), and each copy costs
O(k), so the output takes O(k * C(n, k)). The loop bound keeps the extra calls small. The space isO(k)forpathand the recursion stack.- How do you allow a number to be used many times?
Recurse with
backtrack(i, ...)and notbacktrack(i + 1, ...). The loop still starts atstart. This is Combination Sum (LC 39). You also need a way to stop, such as a remaining sum that reaches 0 or becomes negative.- How do you handle repeated values in the input?
Sort the input. In each call, skip
candidates[i]wheni > startand it equalscandidates[i - 1]. This is Combination Sum II (LC 40). The test usesstartso that the first pick of each call is never skipped.- Why is the loop bound
n - need + 2and notn + 1? A pick
iis useful only if enough larger numbers remain to finish the group. The last usefuliisn - need + 1, andrangestops before its end, so the end isn - need + 2. The answer is the same withn + 1, but more calls run: 638 and not 462 forcombine(10, 5).
SWE Reasoning
Spot it
- The answer is a list of groups, and the order inside a group does not matter.
- Every group must reach a target: a length
k, a sum, or a count of items. - A number may be used once, or many times. The statement says which.
- A partial group that has passed the target can be cut at once, for example when the sum is already too large.
- The input has repeated values and the answer must not list a group twice. Sort and skip the repeat.
The invariant, step by step
backtrack(start)runs. Ifis_complete(path)is True, such aslen(path) == k, it saveslist(path)and returns.- The loop runs
ifromstart. Forcombine, it stops atn - need + 1, because a laterileaves too few numbers. path.append(i)makes the pick.backtrack(i + 1)explores every group that continues with larger numbers.path.pop()removes the pick, so the nextistarts from the samepath.pathis always in increasing order, and every number still allowed is at leaststart. A group has one increasing order, so each group is built once.
Traps
backtrack(start + 1)instead ofbacktrack(i + 1). The next pick can be a number that is already inpath.combine(3, 2)returns[[1, 2], [1, 3], [2, 2], [2, 3]].- A loop that restarts at 0 for reuse. For reuse, change the recursion to
backtrack(i, ...). The loop must still start atstart. A loop from 0 builds[2, 3]and[3, 2]for target 5. - The loop bound one too low.
range(start, n - need + 1)loses every group that ends inn. The end must ben - need + 2. - No skip for repeated values. In Combination Sum II (LC 40), the same number twice starts the same group twice. Sort, then skip when
i > startand the value equals the left neighbour. - Saving
pathand notlist(path). The saved lists change whenpathchanges.