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
nums
are unique.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.
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.
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.
Recursive Step: For each number in the input array, if it hasn't been visited:
n
distinct elements is n!
.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.n
.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.