Permutations - Swap Trick
Permutations - Swap Trick is a medium recursion & backtracking problem solved with the permutations pattern.
The best approach, swap trick (in place), runs in O(n · n!) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from used-array backtracking (for comparison) up.
Problem
Generate every permutation of an array in place by swapping, without a separate used array or path list. It is the same result as Permutations; the goal here is to learn the swap technique.
Examples
Example 1
- Input
nums = [1, 2, 3]- Output
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]- Why
- The order comes from swapping each candidate into position 0, then position 1.
Example 2
- Input
nums = [5, 6]- Output
[5,6] [6,5]
Constraints
1 <= nums.length <= 8
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 |
|---|---|---|
| Used-array backtracking (for comparison) | O(n · n!) | O(n) |
| Swap trick (in place) | O(n · n!) | O(n) |
1Used-array backtracking (for comparison)
O(n · n!)O(n)Build a separate path, marking elements as used. Correct, but it needs a path list and a boolean array.
- For each unused index: mark, add, recurse, unmark, remove.
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;
}
}2Swap trick (in place)
O(n · n!)O(n)Recursion depth only.Permute the array itself. At depth i, swap each index j >= i into position i, recurse on i + 1, then swap back. The prefix nums[0..i-1] is the current partial permutation, so no path list or used array is needed.
- If i == n, record a copy of nums.
- For j from i to n - 1: swap(i, j); recurse(i + 1); swap(i, j).
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
go(nums, 0, out);
return out;
}
private void go(int[] nums, int i, List<List<Integer>> out) {
if (i == nums.length) {
List<Integer> p = new ArrayList<>();
for (int x : nums) p.add(x);
out.add(p);
return;
}
for (int j = i; j < nums.length; j++) {
swap(nums, i, j);
go(nums, i + 1, out);
swap(nums, i, j);
}
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
out: List[List[int]] = []
self.go(nums, 0, out)
return out
def go(self, nums: List[int], i: int, out: List[List[int]]) -> None:
if i == len(nums):
p = [x for x in nums]
out.append(p)
return
for j in range(i, len(nums)):
self.swap(nums, i, j)
self.go(nums, i + 1, out)
self.swap(nums, i, j)
def swap(self, a: List[int], i: int, j: int) -> None:
a[i], a[j] = a[j], a[i]class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> out;
go(nums, 0, out);
return out;
}
private:
void go(vector<int>& nums, int i, vector<vector<int>>& out) {
if (i == (int)nums.size()) {
vector<int> p;
for (int x : nums) p.push_back(x);
out.push_back(p);
return;
}
for (int j = i; j < (int)nums.size(); j++) {
swap(nums, i, j);
go(nums, i + 1, out);
swap(nums, i, j);
}
}
void swap(vector<int>& a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
};function permute(nums) {
const out = [];
go(nums, 0, out);
return out;
}
function go(nums, i, out) {
if (i === nums.length) {
const p = [];
for (const x of nums) p.push(x);
out.push(p);
return;
}
for (let j = i; j < nums.length; j++) {
swap(nums, i, j);
go(nums, i + 1, out);
swap(nums, i, j);
}
}
function swap(a, i, j) { const t = a[i]; a[i] = a[j]; a[j] = t; }Edge cases to test
- One element
- Forgetting to swap back
Hints
Hint 1
Positions 0..i-1 are fixed. Try every element from i..n-1 in position i by swapping it there.
FAQ
What is the best time complexity for Permutations - Swap Trick?
Swap trick (in place) runs in O(n · n!) time and O(n) extra space.
Which pattern does Permutations - Swap Trick use?
It is a recursion & backtracking problem that uses the permutations pattern. Other problems with the same pattern: Permutations, Permutations II, Verbal Arithmetic Puzzle.
Is there a brute force solution for Permutations - Swap Trick?
Yes. Used-array backtracking (for comparison) takes O(n · n!) time and O(n) space. Build a separate path, marking elements as used.
Which edge cases should I test for Permutations - Swap Trick?
One element; Forgetting to swap back.