Permutations

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const res = [];
    const used = Array(nums.length).fill(false);
    backtrack(res, [], nums, used);
    return res;
};

var backtrack = function(res, path, nums, used) {
    if (path.length === nums.length) {
        res.push([...path]);
    } else {
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) { // element already used
                continue;
            }
            path.push(nums[i]);
            used[i] = true;
            backtrack(res, path, nums, used);
            path.pop();
            used[i] = false;
        }
    }
};

We will implement a backtracking (DFS) solution. In our backtrack function, we use res to keep track of all valid permutations recorded so far, path to keep track of the current permutation, nums for all the available numbers, and used for values already in path. Note that since order matters for permutations, our loop must always start from 0.