Permutations#

Given a sequence of numbers without duplicates, return all possible permutations.

Example#

Solution#

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    var target = [];
    recursive(nums, [], target, 0);
    return target;
};

function recursive(nums, tmp, target, deep){
    if(deep === nums.length) {
        target.push([...tmp]);
        return 0;
    }
    for(let i=0; i<nums.length; ++i) {
        if(tmp.includes(nums[i])) continue;
        tmp.push(nums[i]);
        recursive(nums, tmp, target, deep+1);
        tmp.pop();
    }
    
}

Idea#

The overall idea is to use backtracking. During the specific recursion, it is similar to a decision tree. First, define a function for recursion, which passes references to the original array, the temporary array, the target array, and the recursion depth. If the recursion depth is the same as the length of the original array, then make a shallow copy of the temporary array and push it into the target array and end the current recursion. If the recursion depth has not reached the length of the original array, taking the input [1, 2, 3] as an example, when the tmp array is empty, there will be three choices: 1, 2, and 3. When 1 is first added to the tmp array, another recursion will occur, where the second digit will be chosen, which will be 2. Then the third digit will be chosen, which will only be 3. When the tmp array is [1, 2, 3], the next step in the recursion will trigger the boundary condition to shallow copy the tmp array into target, and then the tmp array will be popped out with 3, and the loop for choosing the third digit will end. This recursion will then be completed. Then, in the loop for choosing the second digit, when i is 1, the recursion will also end, and the tmp array will pop out with 2. At this point, when i is 2 in the loop, tmp will push nums[2], which is 3, so the third digit can only be 2, and the tmp array will then be [1, 3, 2], and the boundary condition will be triggered. In summary, during the recursion, the first digit can only be 1, 2, or 3. When the first digit is 1, the second digit can only be 2 or 3. When the second is 2, the third digit can only be 3, and so on.

Daily Question#

Source#