LeetEye LeetEye
Hard Backtracking ~5 min

Combination Sum

backtracking combination-sum

Problem

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. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Examples

Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
2+2+3 = 7, 7 = 7
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Key Insight

Like subsets, but allow reusing elements and track sum against target.

Like subsets, but pass same index (reuse allowed). Stop when sum = target (add result) or > target (prune). Move forward only to avoid duplicates.

How to Approach This Problem

Pattern Recognition: When you see keywords like combination sum backtracking, think Backtracking.

Step-by-Step Reasoning

1 After choosing candidates[i], the next choice can:
Answer: Be candidates[i] again
"Unlimited times" means we can pick the same element again.
2 To avoid duplicate combinations like [2,3] and [3,2]:
Answer: Only pick elements at index >= current
By never going backward, we get only one ordering.
3 We stop exploring when:
Answer: All of the above
Stop if exceeded (invalid), found solution, or no more candidates.
4 We add current combination to result when:
Answer: Current sum equals target
We want exact sum. Add only when target reached.
5 If candidates are sorted and current candidate > remaining:
Answer: Skip this and all larger candidates
If this candidate alone exceeds remaining, so will all larger ones (if sorted).
6 After finding a valid combination:
Answer: Continue exploring other possibilities
We want ALL combinations, not just one.

Solution

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    result = []
    
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return
        
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()
    
    backtrack(0, [], target)
    return result

Complexity Analysis

Time O(n^(target/min))
Space O(target/min)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye