LaunchSchool: An online school for Software Engineers

For the dead-end condition, think about what numbers we should or shouldn't add to our current combination to reach a length of k.

For example, imagine we have a partial combination of [2] when considering our example array of [1, 2, 3, 4] and k set to 2. We shouldn't create a combination of [2, 2]. This isn't a valid combination. Nor should we create a combination of [2, 1], as we've likely already found the combination [1, 2]. What numbers should we consider adding to our partial combination of [2]?

In this problem, like in the one before, we are going to use the backtracking template to solve it:

#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 determine to solve the problem:

1. Terminal Condition
2. Dead-end Condition

Terminal Condition

Once we reach the terminal condition, we can be sure we have a valid solution to the problem. What would that be here?

The problem description hints that we need to find all combinations of "size k." This means that 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;
}

Dead-End Condition

The dead-end condition is trickier in this problem. While it feels similar to the previous one, we can't simply apply the logic from the "Permutations" problem. If we just checked if the element was included, we'd get both [1,2] and [2,1], which is invalid. The same issue would occur if we tried to filter the array.

So, what's left?

The key insight is realizing that when we're looking at a given number, the subsequent numbers we can add to the combination are only those that come after it in the array. Not before, and not the same number.

Suppose we have an array of five elements [1, 2, 3, 4, 5] and we're looking for all combinations of length 3.

After we add 1 as a candidate, only numbers 2, 3, 4, and 5 are valid options. Similarly, after we add the number 2, we can no longer choose 1 and 2, but only 3, 4, and 5.

In other words, we can only move forward once we choose an element. We can achieve this implicitly by slicing the array from idx + 1 of the element, so that element and all elements before it are no longer an option.

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.