Given an array nums of distinct integers, return all possible permutations in any order. For example, given [1,2,3], there are six permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Example
nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
There are 3! = 6 ways to arrange three distinct numbers. Each permutation uses every element exactly once in a different order.
Pick each remaining element for the current position, then recurse to fill the next position with whatever is left. When no elements remain (the path length equals the input length), you have a complete permutation — add it to the results. A set tracks which elements are already used.
Why this works
A permutation uses every element exactly once in some order. At each position, you try placing each unused element, then recurse to fill the remaining positions. The used set prevents picking the same element twice. When all positions are filled, you have a complete permutation.
Step by step
- Base case — when the path length equals the input length, every element has been placed, so record this permutation.
- Try each element — loop through all elements; skip any that are already in use.
- Choose and recurse — mark the element as used, add it to the path, and recurse to fill the next position.
- Backtrack — remove the element from the path and mark it unused, so it can be tried at a different position.
Time: O(n·n!)
Space: O(n)
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
return result;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) { // all positions filled — complete permutation
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, path, used, result);
path.remove(path.size() - 1); // undo choice to try other elements
used[i] = false;
}
}
}
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(nums.size(), false);
backtrack(nums, path, used, result);
return result;
}
private:
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
if (path.size() == nums.size()) { // all positions filled — complete permutation
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, path, used, result);
path.pop_back(); // undo choice to try other elements
used[i] = false;
}
}
};
def permute(nums: list[int]) -> list[list[int]]:
result = []
def backtrack(path, used):
if len(path) == len(nums): # all positions filled — complete permutation
result.append(path[:])
return
for i in range(len(nums)):
if i in used:
continue
used.add(i)
path.append(nums[i])
backtrack(path, used)
path.pop() # undo choice to try other elements at this position
used.remove(i)
backtrack([], set())
return result