# Permutation with Swapping Backtrack

·

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;
};
``````