46. Permutations
Tags: algorithms, leetcode, backtracking
Published: 2024-03-11 16:09:29

## 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:

![Decision tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zbmwlx6zgwi8oz3m0ua4.PNG)

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

![Steps to go through decision tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0nasc5rigxyhuszxk9y4.PNG)

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:


![Decision tree with first level highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mwbv7id9k3qscm4a36cm.PNG)

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:
```typescript
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:


![First branch with second and third level highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xo98wxwcm6zdxip9dwwn.PNG)

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:
```typescript
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`:
```typescript
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:
```typescript
    const comb = [];
```
So, the process of "do something" would look like this:
```typescript
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:
```typescript
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:
```typescript
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.