46. Permutations Medium

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]]

Approach

Input: An integer array nums without duplicate numbers.

Output: Return all possible permutation results.

This problem belongs to Permutation Backtracking problems.

• We need to choose a number at each position, ensuring every number appears exactly once.
• Use path to save the current permutation result.
• Use a set s to keep track of the remaining numbers available to pick.
• When the length of path equals the length of nums, it indicates the current sequence is a complete permutation, and we can save it to the answer.
• After selecting a number, remove it from the available set s, and then recurse into the next level.
• When backtracking, we must undo the choice and remove the number from path.

Three Questions of Backtracking

1. Current Operation?

   • At the current position i (how many numbers selected so far), try selecting an unselected number x from set s to put into the current sequence path.
   • Specifically, adding number x to path, representing "I chose this number".

2. Sub-problem?

   • After choosing number x, we need to recursively construct the rest of the permutation.
   • Namely, continuing to select the next number from s - {x}.

3. Next Sub-problem?

   • The next recursive step is calling dfs(i + 1, s - {x}), processing choices from the remaining candidates until the sequence length equals n.

Pruning Conditions

• A number x can only be selected if it still exists in the set s.
• When the sequence length reaches n, the current permutation is appended to the answer.
• As the problem guarantees no duplicates in nums, we don't need deduplication on the results.

Implementation

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []      # To store all permutations
        path = []     # To store the current permutation path
        n = len(nums) # Length of the array

        def dfs(i, s):
            """
            i: current recursion depth, representing how many numbers are selected
            s: remaining numbers available to be selected (set)
            """
            if i == n:
                # When the permutation length reaches the array length, a valid permutation is formed
                ans.append(path.copy())
                return

            for x in nums:
                # We can only choose number x if it hasn't been chosen yet (exists in s)
                if x in s:
                    path.append(x)          # Choose number x
                    dfs(i + 1, s - {x})    # Recurse to the next level, removing x from set s
                    path.pop()             # Backtrack, undo choice, and try another number

        dfs(0, set(nums))  # Start from layer 0, initially all numbers can be selected
        return ans

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const ans = [];          // Store all the permutations
    const path = [];         // Journey of current permutation
    const unUsed = new Set(nums);  // Track unchosen numbers (Using Set for quick lookup)

    /**
     * @param {number} i Current depth of recursion
     * @param {Set} s   Set of available choices remaining
     */
    function dfs(i, s) {
        // If we have selected nums.length digits, a permutation is found
        if (i === nums.length) {
            ans.push([...path]);  // Store the deep-copy of current valid permutation
            return;
        }

        // Enumerate over all elements to consider
        for (let x of nums) {
            if (s.has(x)) {       // Number chosen must not have been previously visited
                path.push(x);     // Select current digit
                s.delete(x);      // Mark as "used"
                
                dfs(i + 1, s);    // Continue constructing next levels

                // Backtrack: Undo choice
                s.add(x);         // Set back to "unused"
                path.pop();       // Take out of subset representation
            }
        }
    }

    dfs(0, unUsed);  // Start from layer 0, initially the available set is everything
    return ans;      // Return formed permutations
};

Complexity Analysis

• Time Complexity: O(n * n!)
• Space Complexity: O(n * n!)

Links

46. Permutations (English)

46. 全排列 (Chinese)