How to solve Leetcode, 46 permutation?
Let's see a easy way to solve with tree breadth first solution.
For example : [1, 2, 3]
The approach : take an item each time to insert into in between array.
1: [ [1] ]
Insert the first number.
2: [ [1] ]
^ ^
Insert 2 before and after 1.
[[2,1],[1,2]]
3:
[
[3,2,1],[2,3,1],[2,1,3],
// place 3 around and between [ 2,1 ]
^ ^ ^
[3,1,2],[1,3,2],[1,2,3]
// place 3 around and between [ 1,2 ]
^ ^ ^
]
Hope this approach is easy to understand.
var permute = function(nums) {
//init results with first numbers
let results = [[nums[0]]];
//loop through the rest of numbers
for (let i = 1; i<nums.length;i++) {
let num = nums[i];
let tmp=[];
//loop through each item in the results
for (let j=0;j<results.length;j++) {
let result = results[j];
//insert the current number around/in-between
for (let k=0;k<=result.length;k++) {
let head = result.slice(0,k);
let tail = result.slice(k);
tmp.push([...head, num, ...tail]);
}
}
results = tmp;
}
return results;
};
