Problem
Given an array nums of distinct integers, return all possible permutations. The permutations may be returned in any order.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,3]Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Solution
This solution uses Backtracking to generate all possible permutations. At each step, we choose one element that has not yet been used and add it to the current permutation.The recursion continues until the current permutation contains all elements. At that point, a copy of the permutation is added to the result.
After each recursive call, the last element is removed and marked as unused. This backtracking step allows the algorithm to explore other possible arrangements.
public List> permute(int[] nums) {
List> result = new ArrayList<>();
// Track visited elements by their index position
boolean[] visited = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), result, visited);
return result;
}
private void backtrack(int[] nums, List current, List> result, boolean[] visited) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
// O(1) constant time lookup instead of O(N)
if (visited[i]) {
continue;
}
visited[i] = true;
current.add(nums[i]);
backtrack(nums, current, result, visited);
// Undo choices
current.remove(current.size() - 1);
visited[i] = false;
}
}
Complexity
For n elements, there aren! possible permutations. Creating and storing each permutation takes O(n) time, resulting in an overall time complexity of O(n × n!).
The recursion stack, current permutation, and
used array require O(n) extra space, excluding the space required for the output.