Permutations

permutations.js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums, res = [], temp = []) {
    if(nums.length === 0) res.push([...temp]);

    for(let i=0; i<nums.length; i++) {
        // Choose
        temp.push(nums[i]);
        let rest = nums.filter((e, index) => index !== i);
        // Backtrack
        permute(rest, res, temp);
        // Unchoose
        temp.pop();
    }

    return res;
};

// Loop through the array and for every element and choose the current element as starting element, either choose it or dont choose it and store it in temp;
// once all choices have been made, push temp in results array and repeat for the next element

// Time: O(n!)
// Space: O(n)