Back to Open Book Shelf

In this assignment, we'll walk through a backtracking problem mentioned in the previous assignments, "Permutations."

Problem Description

// Create a function `permutations` that takes an array of unique integers, `nums`, and
// returns all possible arrangements (permutations) of these numbers.

// The input array will contain at most 8 numbers.

// Example:

  // Input: [1,2,3]
  // Output: [
  //          [1, 2, 3],[1, 3, 2],[2, 1, 3],
  //          [2, 3, 1], [3, 1, 2], [3, 2, 1]
  //                                          ]

function testPermutations(input, expectedLength) {
  const result = permutations(input);
  if (result.length !== expectedLength) return false;

  const stringifiedPerms = result.map(JSON.stringify);
  const uniquePerms = new Set(stringifiedPerms);
  return uniquePerms.size === expectedLength;
}

// Test Cases:

console.log(testPermutations([1,2,3], 6));
console.log(testPermutations([0,1], 2));
console.log(testPermutations([1], 1));
console.log(testPermutations([1,2,3,4], 24));
console.log(testPermutations([1,2,3,4,5], 120));
console.log(testPermutations([1,2,3,4,5,6], 720));
console.log(testPermutations([1,2,3,4,5,6,7], 5040));
console.log(testPermutations([1,2,3,4,5,6,7,8], 40320));
console.log(testPermutations([0,1,2,3,4,5,6,7,8,9], 3628800));

// Note: The order of permutations in the output doesn't matter,
// as long as all permutations are present.

// Don't run the last case for the naive-branch solution.
// If you do and your machine seems "stuck" press `CTRL+Z`

Walkthrough

Naive Solution

We'll start the problem by drawing the state space tree for a naive branching logic. This might already look familiar from one of the previous assignments.

Let's define what naive branching logic means in this case. It means that whenever we pick a number, when choosing the next possible number, we should start from the beginning of the array. So, even though we chose 1 as the first number, the next possible number would still be 1, and the one after that would also be 1.

When do we stop? We stop when the candidate array (the potential solution we are building) equals the length of the input array. This is our terminal condition.

Now we need to define a dead-end and a success condition.

Since we can't have duplicate values in any permutation, we can check whether all elements in the candidate array are distinct once we reach our terminal condition. If they are, we have a valid solution; if not, we've reached a dead-end.

Let's recap:

  • We are choosing every possible combination of numbers, even those with obvious duplicates.
  • Once we reach a terminal condition where the length of the candidate array is equal to the length of the input array, we have two options:
    • It's a valid solution (all elements are distinct)
    • It's a dead-end (there are duplicates)

Let's now fill in the template with this logic for the terminal condition:

function permutations(candidates) {
  function backtrack(candidates, candidate, results) {
    #highlight
    if (candidate.length === candidates.length) {
      if (isUnique(candidate)) {
        results.push([...candidate]);
      }
      return;
    }
    #endhighlight
    for (let elem of candidates) {
      candidate.push(elem);
      backtrack(candidates, candidate, results);
      candidate.pop();
    }
  }

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

As you can see from the template, we don't have any pruning logic yet within the loop. The only thing we're doing is checking on line 3 whether the candidate array has the same length as the input candidates array. If so, we check if the array is unique. If it is, this is a valid solution, and we can add it to the results array. We haven't implemented the isUnique function yet, but that should be fairly straightforward. Let's see the complete code below:

function permutations(candidates) {
  #highlight
  function isUnique(nums) {
    const seen = new Set();
    for (let entry of nums) {
      if (seen.has(entry)) {
        return false;
      }
      seen.add(entry);
    }
    return true;
  }
  #endhighlight

  function backtrack(candidates, candidate, results) {
    if (candidate.length === candidates.length) {
      if (isUnique(candidate)) {
        results.push([...candidate]);
      }
      return;
    }
    for (let elem of candidates) {
      candidate.push(elem);
      backtrack(candidates, candidate, results);
      candidate.pop();
    }
  }

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

To implement the isUnique function, we use a Set. When we encounter a number, if it's already in the Set, we return false; otherwise, we add it to the Set. If we never return false, we can return true, knowing there are no duplicates.

If you try running the last test case, you might see that it times out or takes very long to compute. For now, remove that test case as we'll soon see how to optimize our function.

Optimization

Now that we have a valid solution using naive branching logic, we want to optimize it by pruning paths that are obviously not part of the valid solution.

There are several ways we could do that. The main logic now will reside within the for loop.

Option 1: Check for Inclusion

Before adding an element to the candidate array, we check if it's already present. If it is, we simply skip that iteration. With this approach, once we reach the terminal condition, we'll already know we have a valid solution, so we won't need to check whether the candidate array is unique. Let's see this in action using the template:

function permutations(candidates) {
  function backtrack(candidates, candidate, results) {
    if (candidate.length === candidates.length) {
      results.push([...candidate]);
      return;
    }
    for (let elem of candidates) {
      #highlight
      if (candidate.includes(elem)) {
        continue;
      }
      #endhighlight
      candidate.push(elem);
      backtrack(candidates, candidate, results);
      candidate.pop();
    }
  }

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

Option 2: Filtering the Collection

Instead of explicitly checking for a dead-end condition, we can implicitly handle it by filtering the candidates array. After adding an element to the candidate array, we remove that element from the candidates array for the next recursive call. This ensures we won't be able to add the same element again, as it won't be present in the filtered candidates array.

However, be careful with this approach, as it changes our terminal condition. While our candidate array is growing, the candidates array is shrinking due to filtering. The terminal condition becomes reaching the point where there are no more elements in the candidates array. Let's see this in code:

function permutations(candidates) {
  function backtrack(candidates, candidate, results) {
    #highlight
    if (candidates.length === 0) {
      #endhighlight
      results.push([...candidate]);
      return;
    }

    for (let elem of candidates) {
      #highlight
      const filteredCandidates = candidates.filter((e) => e !== elem);
      #endhighlight
      candidate.push(elem);
      #highlight
      backtrack(filteredCandidates, candidate, results);
      #endhighlight
      candidate.pop();
    }
  }
  const results = [];
  const candidate = [];
  backtrack(candidates, candidate, results);
  return results;
}

And now, given a bit of time, all test cases should pass. This is a significant improvement over our initial solution as we're eliminating all invalid paths early on. As you can see from the code, we're following the template closely. The only modifications we've made are to the terminal condition or the dead-end condition, while everything else remains the same.

It's worth noting that both options we discussed - checking for inclusion and filtering the collection - achieve the same goal of preventing duplicate elements in our permutations. The choice between them might depend on factors like your input size or personal preference for code readability.

In the next assignment, you'll have the opportunity to solve another problem independently, following the provided template and applying the backtracking logic we've learned. This will be a great chance to reinforce your understanding and practice implementing these concepts independently.

Previous:  Template
Next:  Practice: Combinations