Combination Sum
Problem
Given distinct positive candidates and a target, return every unique combination of candidates that sums to target. Each candidate may be used any number of times, and combinations that differ only in order count once.
Example 1
Input: candidates = [2, 3, 6, 7], target = 7 Output: [[2, 2, 3], [7]]
Also asked as: Combinational Sum
Test cases
Case 1
Input: [2,3,6,7], 7 Expected (any order): [[2,2,3],[7]]
Case 2
Input: [2,3,5], 8 Expected (any order): [[2,2,2,2],[2,3,3],[3,5]]
Case 3
Input: [2], 1 Expected (any order): []
View solutionHide solution1 approach
1. Backttrack, allowing reuse (recurse on the same index)
Time O(2^target)Space O(target / min)
From `start`, try each candidate; subtract it from the target and recurse on `i` (reuse allowed) or `i+1` (no reuse). Sort to prune once a candidate exceeds the remaining target.
function combinationSum(candidates, target) { candidates.sort((a, b) => a - b); const res = [], path = []; const bt = (start, remaining) => { if (remaining === 0) { res.push([...path]); return; } for (let i = start; i < candidates.length && candidates[i] <= remaining; i++) { path.push(candidates[i]); bt(i, remaining - candidates[i]); // i (not i+1) ⇒ reuse allowed path.pop(); } }; bt(0, target); return res;}