Combination Sum

BacktrackingRecursion

25 min

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of `candidates` where the chosen numbers sum to `target`.

Example

Example 1:

Input: candidates = [2,3,6,7], target = 7

[2, 2, 3]

[7]

Output: [[2,2,3],[7]]

Solution

This problem is a classic backtracking problem. We can use a recursive approach to explore all possible combinations. The key is to make a decision at each step: either include the current candidate in our combination and recurse, or skip it and move to the next candidate.

Algorithm Steps

Define a recursive function `backtrack(index, currentSum, currentCombination)`.
If `currentSum` equals `target`, we've found a valid combination. Add it to our results and return.
If `currentSum` exceeds `target` or `index` is out of bounds, we've hit a dead end. Return.
Iterate from `index` to the end of the `candidates` array. This allows us to reuse the same element.
- Add `candidates[i]` to `currentCombination`.
- Recursively call `backtrack(i, currentSum + candidates[i], currentCombination)`. Notice we pass `i`, not `i + 1`.
- Backtrack: remove `candidates[i]` from `currentCombination`.
Initial call: `backtrack(0, 0, [])`.

Combination Sum Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Candidates

Target

Combination

Sum

[]

Valid Solutions

No solutions found yet...

Combination Sum Solution


class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        res = []

        def dfs(i, cur, total):
            if total == target:
                res.append(cur.copy())
                return
            if i >= len(candidates) or total > target:
                return

            cur.append(candidates[i])
            dfs(i, cur, total + candidates[i])
            cur.pop()
            dfs(i + 1, cur, total)

        dfs(0, [], 0)
        return res