46. Permutations

PROBLEM:

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

REASONING:

Let's say we are given this array: [1,2,3]. The process of deriving all permutations is depicted in the following diagram:

To understand what is really happening, let's just focus on the first branch of the decision tree.

The blue arrows in the following diagram illustrate the steps that we will go through, in order. At step 1, we put 1 into our basket. Now, our basket contains the element 1. At step 2, we put 2 into our basket. Now our basket contains 2 elements: 1 and 2. At step 3, we put 3 into our basket. Now our basket contains 3 elements: 1, 2, and 3. At this point, the number of elements in our basket is equal to the number of elements in the given array. We have nothing left to collect. So, we pour all content of our basket into the result array. At step 4, we go back to node 2 while throwing element 3 away. Now, our basket contains only 1 and 2. At step 5, we go back to node 1 while throwing the element 2 away. Now, our basket contains only one element, which is 1. Then, we move to the right branch and do similar things.

Notice that whenever we go back from one node, we throw the value of that node away. For example, when we go back from node 2 to node 1 at step 5, we throw the value 2 away so that our basket from containing 1 and 2 at step 4 now only has 1. This is what the backtracking algorithm does. We examine one branch, get back, clean up after ourselves so that we are ready for another branch.

Now, let's look at the decision tree again:

Notice that at the first level, we examine node 1, then node 2, then node 3. In other words, we examine all nodes of the array, one by one. We can use a for loop for that:

for(let i = 0; i < nums.length; i++) {
        // do something with nums[i]
}

Let's look at the decision tree again, but only the first branch this time:

Notice that at the second level of a branch, we only examine the nodes that we haven't examined at the first level of that branch. Because we've already examined node 1 at the first level, we only need to examine node 2 and node 3 at the second level.

Also, at the third level, we only examine the nodes that we haven't examined at the first and second levels of that branch. For example, on the left branch, because we've already examined node 1 at the first level, and node 2 at the second level, now, we only have node 3 to examine.

So, we need a hash table to mark the node that we've already examined:

const hashTB: Record<string, boolean> = {};

Then, at each level, we will go through the nums array, and only "do something" with the elements that are not in hashTB:

for(let i = 0; i < nums.length; i++) {
   if(!hashTB[nums[i]]) {
       // do something with nums[i]
   }
}

But what is "do something" anyway? Well, it's very simple: put nums[i] into the basket and hashTB.

So, we need a basket. Let's create one:

    const comb = [];

So, the process of "do something" would look like this:

comb.push(num);
hashTB[num] = true;

Notice that, at each level, we repeat this process, only with fewer elements. This calls for a recursive function. Let's call our function backtrack.

So, our function would look like this:

function backtrack(num: number) {
      // do something with the current element.
        comb.push(num);
        hashTB[num] = true;

       // going through all the elements left at the next level
        for(let i = 0; i < nums.length; i++) {
            if(!hashTB[nums[i]]) {
                backtrack(nums[i]);
            }
        }
    }  

Do you remember the clean-up process in our backtracking algorithm? It's just simply setting hashTB[num] to false and using comb.pop() to pop the current value out of the basket.

But how do we know that we've already collected all the elements in nums? Well, it is when comb.length is equal to nums.length.

So, our final code looks like this:

function permute(nums: number[]): number[][] {   
    const comb = [];
    const result: number[][] = [];
    const hashTB: Record<string, boolean> = {};
    const isComplete = () => comb.length === nums.length;

    for(let i = 0; i < nums.length; i++) {
        backtrack(nums[i]);
    }

    return result;

    function backtrack(num: number) {
        comb.push(num);
        hashTB[num] = true;

        for(let i = 0; i < nums.length; i++) {
            if(!hashTB[nums[i]]) {
                backtrack(nums[i]);
            }
        }

        if(isComplete())
            result.push([...comb])

        hashTB[num] = false;
        comb.pop();
    }  
};

This code successfully generates all possible permutations of the given array by utilizing a backtracking algorithm, which explores each branch of the decision tree, collects elements along the way, and cleans up before moving to the next branch.