I talked about how to do permutation before, check my previous article to see the solution.

Today I saw another solution, which I think is pretty clever.

The solution is called swapping backtrack. It's process is well explained in below image(which I take from leetcode).

As you can see in the image, there are 2 loops and the second loop starts from the index of the current one.(In above, index `i`

starts from index `first`

). Whenever we find these 2 index is not equal, we do a swapping.

The most easy way to implement it is to do it recursively. Whenever we find index `i`

is equal to index `first`

, then we find one permutation. If its not equal, then we walk to next level.

```
function permute(nums: number[]): number[][] {
let q: number[][] = [];
function backtrack(first: number) {
if (first === nums.length) {
q.push([...nums]);
} else {
backtrack(first + 1);
const v = nums[first];
for (let i = first + 1; i < nums.length; i++) {
// swapping
nums[first] = nums[i];
nums[i] = v;
backtrack(first + 1);
// swapping back
nums[i] = nums[first];
nums[first] = v;
}
}
}
backtrack(0);
return q;
};
```

We can also implement the same logic iteratively. The key that we don't walk down for each loop, we walk to the next value. You can think of the process is a level traversal. So after current level, remember to delete the previous level results.

```
function permute(nums: number[]): number[][] {
let q: number[][] = [nums];
const n = nums.length;
for (let first = 0; first < n; first++) {
let length = q.length;
for (let j = 0; j < length; j++) {
nums = q[j];
const v = nums[first];
q.push([...nums]);
for (let i = first + 1; i < n; i++) {
nums[first] = nums[i];
nums[i] = v;
q.push([...nums]);
nums[i] = nums[first];
nums[first] = v;
}
}
q = q.slice(length);
}
return q;
};
```