Combination Sum

Medium

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}