Q40: Combination Sum

Given an array of distinct integers candidates and a target, return all unique combinations where candidate numbers sum to target. Numbers can be reused infinitely.

Unbounded Choice Combination Sum

function combinationSum(candidates, target) {
  const result = [];
  
  function backtrack(remain, current, start) {
    if (remain === 0) {
      result.push([...current]);
      return;
    }
    if (remain < 0) return; // Prune branch
    
    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(remain - candidates[i], current, i); // 'i' allows reusing same element
      current.pop();
    }
  }
  
  backtrack(target, [], 0);
  return result;
}

console.log(combinationSum([2, 3, 6, 7], 7)); // [[2, 2, 3], [7]]

💡 Prunes search when remain < 0. When remain === 0, saves combination. Reuses element by passing i to recursive call.

Key Takeaways

Backtracking recursion allows reusing current number by passing index i instead of i + 1.
Prunes exploration branches when remain < 0.

Knowledge Check

Why is the index parameter `i` passed to recursive backtrack(remain - candidates[i], current, i) instead of `i + 1`?

Q40: Combination Sum

STAY UPDATED WITH BYTES!