Combination Sum

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []

Pseudocode

- dfs to recurse through array with backpeddeling
  - push and pop

- understand how the code works, but do not understand this intuitively

Solution

// from solutions
// https://leetcode.com/problems/combination-sum/solutions/16757/javascript-solution-with-backtracking/
var combinationSum = function (candidates, target) {
  const buffer = [];
  const result = [];

  function walk(idx, target) {
    // console.log(buffer)
    // base condition
    if (target === 0) {
      // console.log('found combination')
      // if recursion results in target === 0, then take this combination and push into result
      return result.push(buffer.slice());
    }

    if (target < 0) {
      // console.log('target < 0')
      return;
    }

    if (idx === candidates.length) {
      // console.log('end of arr length')
      return;
    }
    // pre
    // start recursion with this number, if resulting target === 0, then buffer --> result
    buffer.push(candidates[idx]);
    // recurse

    // start recursion with this idx (itself), with after deducting target, find other combinations
    walk(idx, target - candidates[idx]);

    // if code reaches here, then combination < 0 or end of arr, pop it out from buffer and...
    buffer.pop();

    // start searching in the next idx
    walk(idx + 1, target);
    // post
  }

  walk(0, target);

  return result;
};

Time and Space Complexity

Time

What did the code do
Total -

Space

What did the code do
Total -

PreviousSearch in Rotated Sorted Array NextPermutations

Last updated 2 years ago

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

// from solutions // https://leetcode.com/problems/combination-sum/solutions/16757/javascript-solution-with-backtracking/ var combinationSum = function (candidates, target) { const buffer = []; const result = []; function walk(idx, target) { // console.log(buffer) // base condition if (target === 0) { // console.log('found combination') // if recursion results in target === 0, then take this combination and push into result return result.push(buffer.slice()); } if (target < 0) { // console.log('target < 0') return; } if (idx === candidates.length) { // console.log('end of arr length') return; } // pre // start recursion with this number, if resulting target === 0, then buffer --> result buffer.push(candidates[idx]); // recurse // start recursion with this idx (itself), with after deducting target, find other combinations walk(idx, target - candidates[idx]); // if code reaches here, then combination < 0 or end of arr, pop it out from buffer and... buffer.pop(); // start searching in the next idx walk(idx + 1, target); // post } walk(0, target); return result; };