Solution Explanation: 46. Permutations

This problem asks for all possible permutations of a given array of distinct integers. The most efficient way to solve this is using Depth-First Search (DFS) with backtracking.

Approach: DFS (Backtracking)

The core idea is to recursively explore all possible arrangements of the numbers. We maintain a visited array (or a similar mechanism) to track which numbers have already been included in the current permutation.

1. Base Case: If we've filled all positions in our current permutation (the length of the current permutation equals the length of the input array), we've found a complete permutation, so we add it to the result.

2. Recursive Step: For each number in the input array, if it hasn't been visited:

   • Mark the number as visited.
   • Add the number to the current permutation.
   • Recursively call the DFS function to explore the next position.
   • Remove the number from the current permutation (backtracking) and unmark it as visited. This allows us to explore other arrangements.

Time Complexity Analysis

• The number of permutations of n distinct elements is n!.
• In each recursive call, we perform a constant amount of work (checking if a number is visited, adding/removing it to/from the current permutation).
• Therefore, the overall time complexity is O(n * n!), where n is the length of the input array. The n! comes from the number of permutations, and the n factor accounts for the work done in each recursive call to construct and add each permutation to the results array.

Space Complexity Analysis

• The space complexity is O(n) for the recursive call stack. In the worst case, the depth of the recursion is n.
• Additionally, we need O(n) space to store the current permutation and the visited array.
• The space required to store the final result, which contains all the permutations, is O(n * n!). However, this is usually not considered in the space complexity analysis because it's the output size.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#)

The code examples below demonstrate the DFS (backtracking) solution in multiple programming languages. Each implementation follows the same basic structure:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        vis = [False] * n
 
        def dfs(i: int, current: List[int]):
            if i == n:
                ans.append(current[:])  # Add a copy to avoid modification
                return
            for j, num in enumerate(nums):
                if not vis[j]:
                    vis[j] = True
                    dfs(i + 1, current + [num])
                    vis[j] = False  # Backtrack
 
        dfs(0, [])
        return ans

Java:

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] vis;
 
    public List<List<Integer>> permute(int[] nums) {
        vis = new boolean[nums.length];
        dfs(nums, 0, new ArrayList<>());
        return ans;
    }
 
    private void dfs(int[] nums, int i, List<Integer> current) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(current));
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                current.add(nums[j]);
                dfs(nums, i + 1, current);
                current.remove(current.size() - 1); //Backtrack
                vis[j] = false;
            }
        }
    }
}

Other languages (C++, Go, TypeScript, Rust, JavaScript, C#) would have similar implementations, following the same logic of DFS and backtracking. The main differences would be in syntax and data structures. Refer to the original response for complete code in those languages.