LeetCode #39 Medium

Combination Sum

Given distinct candidates and a target, return every unique combination that sums to target. The same number may be reused unlimited times.

backtrackingrecursionarray

Open on LeetCode ↗

02

Intuition

💡

Build combinations by repeatedly choosing a candidate. To avoid duplicate combinations in a different order, only ever pick candidates from the current index onward — that fixes a non-decreasing order.

03

Approach

1

Blind enumeration explodes and duplicates

Generating every possible multiset of candidates and filtering those summing to the target is hopeless: the search space is huge, and it produces the same combination in many orders ([2,2,3], [2,3,2], [3,2,2]). Both problems are solved by structuring the search as a recursion that only ever extends combinations in one direction.

2

Recurse with a start index and a shrinking target

Backtracking explores choices one at a time. Pass a start index and a remaining target down the recursion. At each level you may pick candidates[i] for any i >= start, subtract it from remain, and recurse. The key to allowing reuse is recursing with the same index i (not i + 1), so the same number can be chosen repeatedly. Forcing choices to move forward from start is also what prevents reordered duplicates — combinations are always built in non-decreasing index order.

3

Base case, pruning, and undo

When remain hits exactly 0, we've found a valid combination — append a copy of the current path (not the live list, which keeps mutating). Prune any branch where a candidate exceeds remain, since it can't lead anywhere. After each recursive call, pop the last choice to backtrack and try the next — that undo is what lets one path object explore the whole tree. Roughly O(N^(target/min)) in the worst case.

04

Solution & live demo

python

▶1class Solution:
▶2    def combinationSum(self, candidates, target):
▶3        res = []
▶4        def backtrack(start, remain, path):
▶5            if remain == 0:
▶6                res.append(path[:])
▶7                return
▶8            for i in range(start, len(candidates)):
▶9                c = candidates[i]
▶10                if c <= remain:
▶11                    path.append(c)
▶12                    backtrack(i, remain - c, path)
▶13                    path.pop()
▶14        backtrack(0, target, [])
▶15        return res

05

Edge cases

A candidate larger than target

The remain - c >= 0 guard skips it, so it never enters a combination.

Target reachable many ways

Each distinct multiset is found once because choices only move forward from start.

Reuse of the same number

Recursing with the same start index permits unlimited reuse, e.g. [2,2,3] for target 7.

06

Complexity

Time

O(N^(T/M))

Space

O(T/M)

Branching over N candidates to depth ~target/min; recursion stack is the path depth.