/**
 * https://leetcode.com/problems/permutations/solution/
 * Time O(N!) | Space(N!)
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permute = function(nums) {
    return dfs(nums)
}

var dfs = function(nums, permutation = [], permutations = []) {
    const isBaseCase = nums.length === permutation.length
    if (isBaseCase) return permutations.push(permutation.slice())

    for (let i = 0; i < nums.length; i++) {
        if (permutation.includes(nums[i])) continue;

        backTrack(nums, i, permutation, permutations);
     }

    return permutations;
}

const backTrack = (nums, i, permutation, permutations) => {
    permutation.push(nums[i])
        dfs(nums, permutation, permutations)
    permutation.pop()
}

/**
 * https://leetcode.com/problems/permutations/solution/
 * Time O(N!) | Space(N!)
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    return bfs(nums)
}

const bfs = (nums, levels = [[]], permutations = []) => {
    for (const num of nums) {
        for (let i = (levels.length - 1); 0 <= i; i--) {
            const previousLevel = levels.shift()

            for (let index = 0; index < (previousLevel.length + 1); index++) {
                const level = reArrangeSet(previousLevel, num, index)

                const isBaseCase = level.length === nums.length;
                if (isBaseCase) {
                    permutations.push(level);
                    continue
                }

                levels.push(level)
            }
        }
    }

    return permutations
}

const reArrangeSet = (previousLevel, num, index) => {
    const [ before, after ] = [ previousLevel.slice(0, index), previousLevel.slice(index) ]

    return [...before, num, ...after]
}