Leetcode, 46 - Permutation

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;

};