Combinations & Combination SumCombinations and pruning

01Why it exists

Reach for it when you see:Reach a target sum, choose k of them, order does not matter, elements may be reused or used only once, list every solution, n is small but brute force is still too slow.

02The core idea

A combination is a selection in which order does not count. [2, 3] and [3, 2] are the same thing, so you cannot scan from the beginning at every level the way permutations do. The fix is to carry a start: each level picks only from start rightward, and once index i has been chosen the next level begins at i (reusable) or at i+1 (used only once). Every combination then appears in exactly one order, indices ascending, and the duplicates vanish on their own.

Pruning is what makes backtracking usable at all. The search tree is exponential, so any test that removes a whole subtree is worth running. Combination Sum sorts the candidates first, and inside the for loop, the moment candidates[i] > remain, everything to its right is larger and even less promising, so this is a break, not a continue. C(n, k) instead stops as soon as too few numbers are left to fill k slots. Each of these tests costs O(1), and each one may remove thousands of nodes.

The three steps — make a choice, recurse, undo the choice — are the same as for subsets; the only difference is that start and remain travel down with the recursion. Two things are easy to mix up. Whether an element may be reused decides whether the next level's start is i or i+1. And when the input itself contains duplicate values, sort it first and skip any i where candidates[i] == candidates[i-1] and i > start, because the branch that begins with that value has already been explored at this level.

The complexity has no clean closed form — it depends on the target and on the candidates, and it is usually just written as exponential. What is certain is that without sorting and pruning, every level tries every candidate, while with pruning the size of the tree comes close to the number of branches that are genuinely viable. If the question only asks how many ways there are, or the fewest items needed, and does not want the solutions listed, that is DP territory (Coin Change) — do not reach for backtracking.

03The algorithm

1. 1Sort the candidates first; that is what lets the pruning use break.
2. 2Write dfs(start, remain): when remain == 0, copy path into the answers and return.
3. 3Run a for loop from start to the end. If candidates[i] > remain, break (that is the pruning). If the input has duplicates and i > start and candidates[i] == candidates[i-1], continue.
4. 4Make a choice: path.append(candidates[i]), then recurse into dfs(i, remain - candidates[i]) (reusable) or dfs(i + 1, …) (used only once).
5. 5Undo the choice: path.pop(), then move on to the next i.

04Interactive demo

candidates = [2, 3, 6, 7], target = 7. The recursion stack underneath shows start and remain at every level, and the yellow step is the moment the pruning fires: the candidate is already larger than remain, so the whole loop ends right there.

05Code

Combination Sum (reusable), C(n, k) (pruned on how many are left) and Combination Sum II (used only once, duplicates in the input). All that separates the three is what gets passed as start and what the pruning condition is.

# Combination Sum (LeetCode 39): every number may be reused to reach target
def combination_sum(candidates, target):
    candidates = sorted(candidates)         # sorting is what makes pruning possible (a new list, so the caller's input is untouched)
    ans = []
    path = []

    def dfs(start, remain):
        if remain == 0:                     # hit the target exactly
            ans.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:      # prune: everything to the right is larger, so end the loop
                break
            path.append(candidates[i])      # make a choice
            dfs(i, remain - candidates[i])  # reusable, so the next level still starts at i
            path.pop()                      # undo the choice

    dfs(0, target)
    return ans


# Combinations C(n, k) (LeetCode 77): choose k of 1..n. Prune when too few numbers are left to fill the rest
def combine(n, k):
    ans = []
    path = []

    def dfs(start):
        if len(path) == k:
            ans.append(path[:])
            return
        need = k - len(path)                # how many more to choose
        for i in range(start, n - need + 2):   # from i onward, at least need numbers must remain
            path.append(i)
            dfs(i + 1)                      # each number is used once, so the next level starts at i+1
            path.pop()

    dfs(1)
    return ans


# Combination Sum II (LeetCode 40): each number is used once, and the input has duplicates
def combination_sum2(candidates, target):
    candidates = sorted(candidates)
    ans = []
    path = []

    def dfs(start, remain):
        if remain == 0:
            ans.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue                    # skip a repeated value at the same level
            path.append(candidates[i])
            dfs(i + 1, remain - candidates[i])
            path.pop()

    dfs(0, target)
    return ans


if __name__ == "__main__":
    print(combination_sum([2, 3, 6, 7], 7))         # [[2, 2, 3], [7]]
    print(combine(4, 2))                            # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))
    # [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]] (the two 1s produce [1, 7] only once)

06Practice

• LeetCode 39Combination SumMedium
• LeetCode 40Combination Sum II (used once only, duplicates skipped)Medium
• LeetCode 77CombinationsMedium
• LeetCode 216Combination Sum IIIMedium
• LeetCode 17Letter Combinations of a Phone NumberMedium
• LeetCode 131Palindrome Partitioning (a combination of cut positions)Medium