Permutations

Permutations is the classic ordering problem. You take a set of numbers and list every possible order of them. Here order matters, which makes it different from Subsets. The interviewer wants to see if you can track which numbers are still free to use, and undo cleanly. That tracking is the core skill.

🎯 The Problem

You get an array of distinct numbers. You return every possible ordering of them.

The rules:

• An ordering that uses all the numbers in some sequence is a permutation.
• Order matters. So [1,2,3] and [2,1,3] are different answers.
• Each permutation uses every number exactly once.
• The order of the permutations in the answer does not matter.

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: every possible ordering of all the numbers.

Here is the problem as a tree where each level fixes one position, and each branch picks a number not yet used.

🔁 Approach 1: Swap In Place (Alternative)

The idea in one line: fix each position by swapping every later number into it, then swap back.

How it works:

• At position i, swap each index from i to the end into position i.
• Recurse on position i + 1.
• Swap the numbers back to restore the array.
• At the last position, the array itself is one permutation. Record it.

Why it works:

• It uses no extra used array.
• The array doubles as both the path and the bookkeeping.

Why it is trickier:

• The swap-back is easy to forget, which corrupts later branches.
• The output order is harder to predict than the used-array version.

Here is the in-place swap code for that idea:

def permute(nums):
    result = []

    def dfs(index):
        if index == len(nums):
            result.append(nums[:])
            return
        for i in range(index, len(nums)):
            nums[index], nums[i] = nums[i], nums[index]
            dfs(index + 1)
            nums[index], nums[i] = nums[i], nums[index]

    dfs(0)
    return result

⚡ Approach 2: Backtracking With a Used Array (Best)

The idea in one line: build the ordering step by step, track which numbers are taken with a flag list, and undo cleanly.

How backtracking works here:

• Build a candidate step by step. Recurse deeper. Then undo the last choice.
• The candidate is the ordering built so far.

Why a used array:

• Unlike Subsets, we do not move a start index forward.
• A permutation may pick a number that sits earlier in the array.
• A used array is a list of true and false flags, one per number.
• Each flag says whether that number is already in the path.

How it works:

• At each level loop over every number.
• Already used, skip it.
• Otherwise mark it used, add it to the path, recurse to fill the next position.
• On return, remove the number and mark it unused. That un-choose step frees it for other branches.

When a path finishes:

• The path holds all the numbers. It is a complete permutation.
• Record a copy and stop that branch.
• The recursion depth equals the count of numbers.

The picture below dry-runs [1, 2, 3]. Marking and un-marking the used flags lets each number appear in every position.

Steps to Solve

1. Create a result list, a path for the current ordering, and a used array of all false.
2. Start a recursive helper.
3. If the path length equals the number count, record a copy of the path and return.
4. Loop over every index in the array.
5. If that index is already used, skip it.
6. Mark the index used and add its number to the path. This is the choose step.
7. Recurse to fill the next position.
8. Remove the number and mark the index unused again. This is the un-choose step.

#include <stdio.h>

int nums[] = {1, 2, 3};
int n = 3;
int path[3];
int used[3];

void printPerm(void) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", path[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
}

void backtrack(int len) {
    if (len == n) { printPerm(); return; }   // full ordering
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;               // skip taken numbers
        used[i] = 1;                         // choose
        path[len] = nums[i];
        backtrack(len + 1);                  // explore
        used[i] = 0;                         // un-choose
    }
}

int main(void) {
    backtrack(0);
    return 0;
}

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> result;
vector<int> path;

void backtrack(vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) { result.push_back(path); return; } // full
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;            // skip taken numbers
        used[i] = true;                   // choose
        path.push_back(nums[i]);
        backtrack(nums, used);            // explore
        path.pop_back();                  // un-choose
        used[i] = false;
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<bool> used(nums.size(), false);
    backtrack(nums, used);
    for (auto& p : result) {
        cout << "[";
        for (int i = 0; i < (int)p.size(); i++) {
            cout << p[i];
            if (i < (int)p.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }
    return 0;
}

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    static void backtrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {            // full ordering
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;                   // skip taken numbers
            used[i] = true;                          // choose
            path.add(nums[i]);
            backtrack(nums, used);                   // explore
            path.remove(path.size() - 1);            // un-choose
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        backtrack(nums, new boolean[nums.length]);
        System.out.println(result);
    }
}

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

def permute(nums):
    result = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):      # path holds every number
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:                 # this number is already in the path
                continue
            used[i] = True              # choose
            path.append(nums[i])
            backtrack()                 # explore
            path.pop()                  # un-choose
            used[i] = False

    backtrack()
    return result


print(permute([1, 2, 3]))

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {  // path holds every number
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;            // this number is already in the path
      used[i] = true;                   // choose
      path.push(nums[i]);
      backtrack();                      // explore
      path.pop();                       // un-choose
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3])));

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Let us walk through the Python version line by line, because the used array is what makes permutations different.

used = [False] * len(nums) builds a flag list, one per number, all false at the start. Each flag says whether that number is already in the current path.

if len(path) == len(nums) checks for a complete ordering. When the path holds every number, it is a full permutation, so we record a copy with path[:] and return. The copy is needed because the path keeps changing.

for i in range(len(nums)) loops over every index. Notice we start at 0 every time, not from a moving start index. That is the key difference from Subsets, because a permutation may use a number that sits earlier in the array.

if used[i]: continue skips a number that is already in the path. This stops us from using the same number twice in one ordering.

used[i] = True and path.append(nums[i]) are the choose step. We mark the number taken and add it to the path.

backtrack() is the explore step. It fills the next position.

path.pop() and used[i] = False are the un-choose step. After the branch returns, we remove the number and mark it free again. This frees the number so other branches can place it in a different position. Forget the used[i] = False line and your later branches would think the number is still taken.

⏱️ Time and Space Complexity

There are n factorial permutations of n distinct numbers, written n!. So just listing them is already that many. Backtracking builds each one and copies it, which costs n per copy. So the total time is O(n times n!). The extra space, not counting the output, is O(n) for the recursion depth, the path, and the used array.

🧩 Key Takeaways

• ✅ A permutation is an ordering that uses every number exactly once.
• ✅ Order matters here, so [1,2,3] and [2,1,3] are different answers.
• ✅ Use a used array to track which numbers are already in the path.
• ✅ The loop starts at 0 every level, not from a moving start index.
• ✅ The un-choose step must reset both the path and the used flag.

🚀 What’s Next?

• Subsets
• Combination Sum