Log inSign up
mediumLeetCodeNot Started

Permutations

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Given an array nums of distinct integers, return *all the possible permutations*. You can return the answer in any order.

Example 1 · 3-Element Permutations:

Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: All 3! = 6 unique orderings of [1, 2, 3].

Example 2 · 2-Element Permutations:

Input: nums = [0, 1]
Output: [[0, 1], [1, 0]]
Explanation: 2! = 2 orderings.

Example 3 · Single Element:

Input: nums = [1]
Output: [[1]]
Explanation: 1! = 1 permutation.

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master in-place array permutation generation without auxiliary memory.
  • Understand the state restoration invariant in depth-first search.
  • Derive the exact runtime O(N! * N) accounting for array copy overhead.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate all possible orderings of N items
  • All elements in the input are strictly distinct
  • Order of elements in the output matters (unlike combinations)

Algorithmic Decision Tree:

  • Use in-place swap backtracking with state start.
  • For i from start to N - 1: swap(nums[start], nums[i]), recurse start + 1, swap(nums[start], nums[i]).
  • When start == nums.length, capture snapshot of nums.

Connected Patterns:

Permutations IINext PermutationSubsetsCombinations

1. Backtracking with Visited/Used Boolean Array

Intuition

Maintain current list and used boolean array. At each step, iterate through all N numbers. If !used[i], mark used[i] = true, push nums[i], recurse, and backtrack.

When to apply: Intuitive first approach maintaining a separate path list.

Algorithm

  1. In solve(current):
  2. - If current.length == nums.length, add copy of current to result.
  3. - For i from 0 to nums.length - 1:
  4. - If !used[i]:
  5. - used[i] = true, current.push(nums[i]).
  6. - Recurse solve(current).
  7. - current.pop(), used[i] = false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void solve(const vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == nums.size()) {
9 result.push_back(current);
10 return;
11 }
12
13 for (int i = 0; i < nums.size(); i++) {
14 if (!used[i]) {
15 used[i] = true;
16 current.push_back(nums[i]);
17 solve(nums, used, current, result);
18 current.pop_back(); // backtrack
19 used[i] = false;
20 }
21 }
22 }
23
24public:
25 vector<vector<int>> permute(vector<int>& nums) {
26 vector<vector<int>> result;
27 vector<bool> used(nums.size(), false);
28 vector<int> current;
29 solve(nums, used, current, result);
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> nums = {1, 2, 3};
37 auto res = sol.permute(nums);
38 for (const auto& p : res) {
39 cout << "[ ";
40 for (int v : p) cout << v << " ";
41 cout << "] ";
42 }
43 cout << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N! * N) — Explores N! permutations with O(N) array copy at leaves.
  • Space complexity: O(N) — Requires used array and current list of size N.

2. Iterative Next Permutation Generation

Intuition

Sort nums. Compute N! permutations iteratively: find pivot from right where nums[i] < nums[i+1], swap with successor, and reverse suffix. Repeat N! times.

When to apply: When generating permutations iteratively without recursion or call stack overhead.

Algorithm

  1. Sort nums in ascending order.
  2. Add nums to result.
  3. While nextPermutation(nums) is true:
  4. - Add copy of nums to result.
  5. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> permute(vector<int>& nums) {
10 vector<vector<int>> result;
11 sort(nums.begin(), nums.end());
12 do {
13 result.push_back(nums);
14 } while (next_permutation(nums.begin(), nums.end()));
15 return result;
16 }
17};
18
19int main() {
20 Solution sol;
21 vector<int> nums = {1, 2, 3};
22 auto res = sol.permute(nums);
23 for (const auto& p : res) {
24 cout << "[ ";
25 for (int v : p) cout << v << " ";
26 cout << "] ";
27 }
28 cout << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generates each of the N! permutations in O(N) average time per transition.
  • Space complexity: O(1) — Uses constant auxiliary memory.

3. In-Place Swap Backtracking (Optimal)

Intuition

Eliminates the need for used boolean array and intermediate path arrays. Placing each candidate at position start via swapping, recursing on start + 1, and restoring via a second swap achieves optimal speed and minimal memory.

When to apply: The gold-standard in-place optimal permutation algorithm.

Algorithm

  1. In backtrack(start, nums):
  2. - If start == nums.length, append copy of nums to result and return.
  3. - For i from start to nums.length - 1:
  4. - Swap nums[start] and nums[i].
  5. - Recurse backtrack(start + 1, nums).
  6. - Swap nums[start] and nums[i] (backtrack).

In-Place Swap Permutation Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initial state: nums = [1, 2, 3], start = 0
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
0
1
2
Variables at this step
start
0
nums
[1,2,3]
Why this step matters

Initial state: nums = [1, 2, 3], start = 0. Choice 1: Swap index 0 with 0 (keep 1 at pos 0).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void backtrack(int start, vector<int>& nums, vector<vector<int>>& result) {
8 if (start == nums.size()) {
9 result.push_back(nums);
10 return;
11 }
12
13 for (int i = start; i < nums.size(); i++) {
14 swap(nums[start], nums[i]);
15 backtrack(start + 1, nums, result);
16 swap(nums[start], nums[i]); // backtrack
17 }
18 }
19
20public:
21 vector<vector<int>> permute(vector<int>& nums) {
22 vector<vector<int>> result;
23 backtrack(0, nums, result);
24 return result;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {1, 2, 3};
31 auto res = sol.permute(nums);
32 for (const auto& p : res) {
33 cout << "[ ";
34 for (int v : p) cout << v << " ";
35 cout << "] ";
36 }
37 cout << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generates all N! permutations with N recursive calls per path and an O(N) array copy at base case.
  • Space complexity: O(N) — Auxiliary space is solely the O(N) call stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Backtracking with Visited ArrayO(N! * N)O(N)Track element usage in boolean array and build path.Boolean array iteration
2.Iterative Next PermutationO(N! * N)O(1)Find next lexicographical permutation repeatedly.Pivot scan and suffix reversal
3.In-Place Swap BacktrackingOptimalO(N! * N)O(N)Swap elements directly in input array with state restoration.Array copy at leaf nodes

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the second swap swap(nums[start], nums[i]) after the recursive call (corrupting array state for sibling branches).

Pitfall 2:

Modifying input array and appending reference instead of a cloned copy.

Crucial Edge Cases to Validate:

  • Single Element: nums = [1] -> returns [[1]].
  • Two Elements: nums = [0, 1] -> returns [[0, 1], [1, 0]].
  • Negative Numbers: nums = [-1, 2, -3] -> handles negative values identically.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the in-place swap method as the most memory-efficient approach.
  2. Mention that while in-place swaps generate all permutations, they do not produce them in lexicographical order (if lexicographical order is required, use Next Permutation or used array on sorted input).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does swap(nums[start], nums[i]) followed by another swap(nums[start], nums[i]) guarantee correct backtracking?

2.How many permutations exist for an array of 5 distinct integers?

Back to DSA Sheet