Problem Statement

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

A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement.

Additional information

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

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

Iterative Insertion (Brute Force)

Intuition

A highly intuitive, albeit brute-force, way to think about building permutations is by inserting numbers one by one into every possible position of previously built permutations.

Imagine we start with an empty permutation [[]].
When we process the first number 1, we can only place it in one spot: [[1]].
When we process the next number 2, we take all our existing permutations (just [1]) and insert 2 at every possible index (index 0 and index 1). This gives us [[2, 1], [1, 2]].
When we process 3, we take [2, 1] and insert 3 at index 0, 1, and 2. Then we take [1, 2] and insert 3 at index 0, 1, and 2.

We cascade this insertion process for every number in the array until we've built all complete permutations.

Algorithm

1. Initialize a list of permutations perms with an empty list inside: [[]].
2. Iterate through each number num in the nums array.
3. For each number, create a fresh empty list new_perms to hold the permutations for this round.
4. Iterate through each existing permutation p in perms.
5. Iterate through every possible insertion index i from 0 to len(p) (inclusive).
6. Create a copy of p, insert num at index i, and append this newly formed list to new_perms.
7. Update perms = new_perms.
8. Return perms.

def permute(nums: list[int]) -> list[list[int]]:
    perms = [[]]
    
    for num in nums:
        new_perms = []
        for p in perms:
            # Insert the current number at every possible position
            for i in range(len(p) + 1):
                p_copy = p.copy()
                p_copy.insert(i, num)
                new_perms.append(p_copy)
        perms = new_perms
        
    return perms

Time & Space Complexity

• Time complexity: O(N * N!)

• Reason: For an array of length N, there are exactly N! (N-factorial) permutations. We must generate all of them. Constructing each permutation involves copying an array of up to size N, which makes the total time heavily bound by O(N * N!).

• Space complexity: O(N * N!)

• Reason: We must store all N! permutations to return them, and each permutation takes up O(N) space. The temporary new_perms array also requires this much space during the final iteration.

Recursive Backtracking (DFS) - Optimal

Intuition

We can build permutations much more elegantly using a Depth-First Search (DFS) decision tree.

At the very top of the tree, we have a blank permutation. We can choose any number from the input array to be our first element. Once we pick a number, we move down a level in the tree. Now, we can pick any number except the one we just used. We keep branching down until our current permutation is exactly as long as the input array.

Because all numbers in the input are unique, we can easily check if a number has already been used by seeing if it's currently inside our growing path. When we reach the bottom of the tree (a full permutation), we backtrack-we pop the last number off so we can go back up and explore a different branch.

Algorithm

1. Initialize an empty list res for our final permutations.
2. Create a recursive helper function dfs(current_perm).
3. Base Case: If the length of current_perm is equal to the length of nums, we have a complete permutation. Append a .copy() of it to res and return.
4. Recursive Step: Loop through every num in nums.
5. If num is already inside current_perm, skip it (we can't use the same number twice).
6. If it's available, append num to current_perm.
7. Recursively call dfs(current_perm) to pick the next number.
8. Backtrack: Pop the last element off current_perm so the loop can move on and try placing the next available number in this slot instead.
9. Call dfs([]) to start and return res.

def permute(nums: list[int]) -> list[list[int]]:
    res = []
    
    def dfs(current_perm):
        # Base case: we have placed all numbers
        if len(current_perm) == len(nums):
            res.append(current_perm.copy())
            return
            
        for num in nums:
            # Skip if the number is already used in the current path
            if num in current_perm:
                continue
                
            # Include the number and explore
            current_perm.append(num)
            dfs(current_perm)
            
            # Backtrack
            current_perm.pop()
            
    dfs([])
    return res

Time & Space Complexity

• Time complexity: O(N * N!)

• Reason: The number of nodes in the backtracking decision tree is proportional to N!. At each leaf node (when a permutation is complete), we copy the array of size N, resulting in O(N * N!) total time. The num in current_perm check takes up to O(N) time, but because the maximum constraint for N is extremely small (N <= 6), this behaves like an O(1) operation.

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space is strictly bounded by the maximum depth of the recursion stack and the current_perm list, both of which never exceed a size of N.