Combination Sum
Module 16 · Recursion & Backtracking
Problem
Given an array of distinct positive integers candidates and a
target integer target, return all unique combinations of candidates
that sum to target. The same candidate may be chosen an unlimited
number of times. Two combinations are the same if they use the same
numbers the same number of times (order doesn't matter).
Examples
Example 1
candidates = [2,3,6,7], target = 7Output[[2,2,3], [7]]Example 2
candidates = [2,3,5], target = 8Output[[2,2,2,2], [2,3,3], [3,5]]Example 3
candidates = [2], target = 1Output[]Explanation. can't reach 1
Constraints
1 ≤ candidates.length ≤ 30 · 2 ≤ candidates[i] ≤ 40 · all distinct · 1 ≤ target ≤ 40. It's guaranteed the number of unique combinations fits in reasonable bounds for these limits.
Attempt it first
Two features make this different from Subsets and Permutations, and both
change the recursion in a specific way: (1) there's now a running
target — a numeric constraint that decides when a path is a valid
answer and when it's a dead end — and (2) reuse is unlimited — the
same number can appear many times. Before reading on, think hard about
what the reuse rule does to the start index you'd use for a
subset/combination. Specifically: after you pick candidates[i], what
should the next call's start index be — i or i + 1? Your answer to
that is the entire trick.