46. Permutations

Problem

https://leetcode.com/problems/permutations/

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution

Solution1

Since the numbers are distinct, we can view this as a progressive adding process. Say we already have the result of i numbers. Now we only need to add the number nums[i+1] into every position of every list in the result.

For example:
result of [1,2] is:

[
  [1,2],
  [2,1]
]

Now add 3 every position of [1,2]. So we got:

[
  [3,1,2],
  [1,3,2],
  [1,2,3],
  [2,1]
]

Same with [2,1]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = []

    nums.forEach(num => {
        if (result.length <= 0) {
            result.push([num])
        } else {
            let newResult = []
            result.forEach(res => {
                for (let i = 0; i <= res.length; i += 1) {
                    let resClone = res.slice()
                    // add the number
                    resClone.splice(i, 0, num)
                    newResult.push(resClone)
                }
            })
            result = newResult
        }
    })

    return result
};

Solution2

Recursion.

For example, in the result

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

For the first position, it would one of the number in [1,2,3].
If you pick 1, then for the second position it would one of the number in [2,3].
So on...

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = []

    function permuteHelper(levelRes, levelNums) {
        if (levelRes.length === nums.length) {
            result.push(levelRes)
        } else {
            for (let i = 0; i < levelNums.length; i += 1) {
                let resClone = levelRes.slice()
                resClone.push(levelNums[i])

                let numsClone = levelNums.slice()
                numsClone.splice(i, 1)

                permuteHelper(resClone, numsClone)
            }
        }
    }

    permuteHelper([], nums)

    return result
};