Permutations
Permutations is a medium recursion & backtracking problem solved with the permutations pattern.
The best approach, optimal (backtracking with a used array), runs in O(n · n!) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from insert into every position up.
Problem
Given an array of distinct integers, return all possible orderings (permutations) of them, in any order.
Examples
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]]
Constraints
1 <= nums.length <= 6, distinct values.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 7 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Insert into every position | O(n · n!) | O(n · n!) |
| Optimal (backtracking with a used array) | O(n · n!) | O(n) |
1Insert into every position
O(n · n!)O(n · n!)Build permutations of the first i elements, then insert nums[i] at every possible position of each.
- Start with [[]].
- For each x, for each partial p, for each position k, insert x at k.
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> perms = new ArrayList<>();
perms.add(new ArrayList<>());
for (int x : nums) {
List<List<Integer>> next = new ArrayList<>();
for (List<Integer> p : perms)
for (int k = 0; k <= p.size(); k++) {
List<Integer> q = new ArrayList<>(p);
q.add(k, x);
next.add(q);
}
perms = next;
}
return perms;
}
}class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
perms: List[List[int]] = [[]]
for x in nums:
next_perms: List[List[int]] = []
for p in perms:
for k in range(len(p) + 1):
q = p[:]
q.insert(k, x)
next_perms.append(q)
perms = next_perms
return permsclass Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> perms;
perms.push_back({});
for (int x : nums) {
vector<vector<int>> next;
for (auto& p : perms)
for (int k = 0; k <= (int)p.size(); k++) {
vector<int> q(p);
q.insert(q.begin() + k, x);
next.push_back(q);
}
perms = next;
}
return perms;
}
};function permute(nums) {
let perms = [[]];
for (const x of nums) {
const next = [];
for (const p of perms)
for (let k = 0; k <= p.length; k++) {
const q = [...p];
q.splice(k, 0, x);
next.push(q);
}
perms = next;
}
return perms;
}2Optimal (backtracking with a used array)
O(n · n!)n! permutations, each copied in O(n). This matches the output size.O(n)At each depth, try every element not yet used, mark it, recurse, then unmark. When the path has n elements it is a full permutation.
- If path.size() == n, record a copy.
- For each i not used: mark, add, recurse, remove, unmark.
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
go(nums, new boolean[nums.length], new ArrayList<>(), out);
return out;
}
private void go(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
go(nums, used, path, out);
path.remove(path.size() - 1);
used[i] = false;
}
}
}class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
out: List[List[int]] = []
self.go(nums, [False] * len(nums), [], out)
return out
def go(self, nums: List[int], used: List[bool], path: List[int], out: List[List[int]]) -> None:
if len(path) == len(nums):
out.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
self.go(nums, used, path, out)
path.pop()
used[i] = Falseclass Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> out;
vector<bool> used(nums.size(), false);
vector<int> path;
go(nums, used, path, out);
return out;
}
private:
void go(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
if (path.size() == nums.size()) { out.push_back(path); return; }
for (int i = 0; i < (int)nums.size(); i++) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
go(nums, used, path, out);
path.pop_back();
used[i] = false;
}
}
};function permute(nums) {
const out = [];
go(nums, new Array(nums.length).fill(false), [], out);
return out;
}
function go(nums, used, path, out) {
if (path.length === nums.length) { out.push([...path]); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
go(nums, used, path, out);
path.pop();
used[i] = false;
}
}Edge cases to test
- Single element
Hints
Hint 1
Unlike combinations, order matters: at each position, any unused element can go next.
FAQ
What is the best time complexity for Permutations?
Optimal (backtracking with a used array) runs in O(n · n!) time and O(n) extra space. n! permutations, each copied in O(n). This matches the output size.
Which pattern does Permutations use?
It is a recursion & backtracking problem that uses the permutations pattern. Other problems with the same pattern: Permutations - Swap Trick, Permutations II, Verbal Arithmetic Puzzle.
Is there a brute force solution for Permutations?
Yes. Insert into every position takes O(n · n!) time and O(n · n!) space. Build permutations of the first i elements, then insert nums[i] at every possible position of each.
Which edge cases should I test for Permutations?
Single element.