Here's our backtracking template:

#highlight
function combinations(candidates, k) {
#endhighlight
  function backtrack(candidates, candidate, result) {
    if (/* <<success condition>> */) {
      result.push([...candidate]);
      return;
    }

    for (let elem of candidates) {
      if (true) {
        continue;
      }

      candidate.push(elem);
      backtrack(candidates, candidate, result);
      candidate.pop();
    }
  }

  const result = [];
  const candidate = [];
  backtrack(candidates, candidate, result);
  return result;
}

We've updated the problem name and function definition to include an additional argument, k, that the function will receive.

Let's jump straight into the optimal approach by pruning invalid paths. There are two main things we need to use to solve the problem:

1. Terminal Condition
2. Dead-end Condition

Remember our terminal condition from above: We've reached the terminal condition whenever the candidate array has a length of k. Let's add that into the template.

function combinations(candidates, k) {
  function backtrack(candidates, candidate, result) {
    #highlight
    if (candidate.length === k) {
    #endhighlight
      result.push([...candidate]);
      return;
    }

    for (let elem of candidates) {
      // if (true) {  // replace true with the dead-end condition
      //   continue;
      // }

      candidate.push(elem);
      backtrack(candidates, candidate, result);
      candidate.pop();
    }
  }

  const result = [];
  const candidate = [];
  backtrack(candidates, candidate, result);
  return result;
}

Now we'll implement the dead-end condition in our template. We've been using for..ofsyntax to iterate through the array, so we didn't have access to the index. We can easily fix this by using a regular for loop. Then, we just need to slice the array from idx + 1, which includes the element after the current one going forward, eliminating all invalid elements.

function combinations(candidates, k) {
  function backtrack(candidates, candidate, result) {
    if (candidate.length === k) {
      result.push([...candidate]);
      return;
    }
    #highlight
    for (let idx = 0; idx < candidates.length; idx++) {
      const elem = candidates[idx];
      candidate.push(elem);
      backtrack(candidates.slice(idx + 1), candidate, result);
    #endhighlight
      candidate.pop();
    }
  }

  const result = [];
  const candidate = [];
  backtrack(candidates, candidate, result);
  return result;
}

This approach solves the problem. However, note that we're slicing the array in every recursive call, which can be costly, especially with large arrays and in languages where slicing is not optimized (more about this in the info section).

Another option is to use another variable, an integer pointing to the beginning of the array. We'll call this variable position. If the position is at 0, we're looking at the whole array.

If it's at 2, we're looking at the array from index 2 going forward.

Let's update the template to use the position variable.

function combinations(candidates, k) {
  function backtrack(candidates, candidate, result, position) {
    if (candidate.length === k) {
      result.push([...candidate]);
      return;
    }
    for (let idx = position; idx < candidates.length; idx++) {
      const elem = candidates[idx];
      candidate.push(elem);
      backtrack(candidates, candidate, result, idx + 1);
      candidate.pop();
    }
  }

  const result = [];
  const candidate = [];
  let position = 0;
  backtrack(candidates, candidate, result, position);
  return result;
}

There are two main differences you should be aware of:

• We now iterate from position until the end of the array, as position marks the beginning of the array.
• When we call the backtrack function, instead of slicing the array, we pass its new beginning, which will be idx + 1, so the original array stays intact. Otherwise, the logic remains the same.