Generate All Permutations

Say you have three friends and three chairs in a row. You want to write down every seating order. Should Alex sit first, or Riya? Then who sits next? Listing all those orders by hand gets messy fast. That is exactly the problem permutations solve.

A permutation is one possible ordering of all the items in a set. Take the set [1, 2, 3]. The orderings are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. So there are six. Our job here is to make the computer produce all of them. No guessing, and nothing missed.

🎯 What We Are Trying to Do

We start with a list like [1, 2, 3]. We want every arrangement that uses each number exactly once.

The trick we use is called backtracking. Backtracking means we build an answer one step at a time. When one path is finished, we step back and try the next choice. Think of trying keys on a keyring. You try one key, it does not fit, so you go back and try the next.

The idea is simple. We fill the arrangement one position at a time. At each position we try every number that we have not used yet. After placing a number, we move on to the next position. When the arrangement is full, we record it. Then we undo the last choice and try a different number.

That “undo and try again” part is the heart of backtracking.

🪑 The Three Chairs Picture

Let us walk through [1, 2, 3] slowly. We have three empty slots to fill.

For the first slot we can pick 1, 2, or 3. Say we pick 1. Now 1 is used. For the second slot we can pick 2 or 3. Say we pick 2. Now only 3 is left, so the third slot must be 3. That gives us [1, 2, 3].

Now we go back. We undo 3, then undo 2, and try 3 in the second slot instead. That gives [1, 3, 2]. We keep doing this until the first slot has tried 1, then 2, then 3.

This tree shows the choices when we start with 1.

The same branching happens when we start with 2 and when we start with 3. So in total we get six leaves, which are our six permutations.

🔖 How We Track What Is Used

We need a way to know which numbers are already sitting in the arrangement. We use a used array. It is a list of true/false flags, one for each number.

The flags do a few small jobs. Before we pick a number, we check its flag. If it is already true, we skip it. When we pick a number, we set its flag to true. When we undo that number, we set its flag back to false.

This stops the same number from showing up twice in one arrangement. Without it, we would get bad orderings like [1, 1, 1].

🪜 Steps to Generate All Permutations

Now we turn the idea into code. We use a recursive helper that fills one position at a time.

1. Keep a current list for the arrangement we are building, and a used array for the flags.
2. If current has the same length as the input, we have a full arrangement. Record a copy of it and return.
3. Otherwise, loop over every index in the input.
4. If that index is already used, skip it.
5. Mark it used, add its value to current.
6. Call the helper again to fill the next position.
7. After the call returns, undo: remove the value from current and mark the index unused.
8. When the loop ends, all choices for this position have been tried.

That step 7 undo is what lets us reuse the same number on a different branch.

💻 The Code

Each version builds a current list, uses a used array of flags, and prints every full arrangement. We run it on [1, 2, 3].

#include <stdio.h>

#define N 3

// current holds the arrangement so far, used marks taken numbers
void permute(int *nums, int n, int *current, int *used, int depth) {
    if (depth == n) {            // arrangement is full
        printf("[");
        for (int i = 0; i < n; i++) {
            printf("%d", current[i]);
            if (i < n - 1) printf(", ");
        }
        printf("]\n");
        return;
    }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;   // skip numbers already placed
        used[i] = 1;             // mark used
        current[depth] = nums[i];
        permute(nums, n, current, used, depth + 1); // fill next slot
        used[i] = 0;             // undo the choice (backtrack)
    }
}

int main(void) {
    int nums[N] = {1, 2, 3};
    int current[N];
    int used[N] = {0, 0, 0};
    permute(nums, N, current, used, 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;

// current holds the arrangement so far, used marks taken numbers
void permute(vector<int>& nums, vector<int>& current, vector<bool>& used) {
    if (current.size() == nums.size()) {   // arrangement is full
        cout << "[";
        for (size_t i = 0; i < current.size(); i++) {
            cout << current[i];
            if (i < current.size() - 1) cout << ", ";
        }
        cout << "]\n";
        return;
    }
    for (size_t i = 0; i < nums.size(); i++) {
        if (used[i]) continue;             // skip numbers already placed
        used[i] = true;                    // mark used
        current.push_back(nums[i]);
        permute(nums, current, used);      // fill next slot
        current.pop_back();                // undo the choice (backtrack)
        used[i] = false;
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> current;
    vector<bool> used(nums.size(), false);
    permute(nums, current, used);
    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 {
    // current holds the arrangement so far, used marks taken numbers
    static void permute(int[] nums, List<Integer> current, boolean[] used) {
        if (current.size() == nums.length) {   // arrangement is full
            System.out.println(current);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;             // skip numbers already placed
            used[i] = true;                    // mark used
            current.add(nums[i]);
            permute(nums, current, used);      // fill next slot
            current.remove(current.size() - 1); // undo the choice (backtrack)
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        permute(nums, new ArrayList<>(), new boolean[nums.length]);
    }
}

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

# current holds the arrangement so far, used marks taken numbers
def permute(nums, current, used, result):
    if len(current) == len(nums):      # arrangement is full
        result.append(current[:])      # store a copy
        return
    for i in range(len(nums)):
        if used[i]:                    # skip numbers already placed
            continue
        used[i] = True                 # mark used
        current.append(nums[i])
        permute(nums, current, used, result)  # fill next slot
        current.pop()                  # undo the choice (backtrack)
        used[i] = False


def all_permutations(nums):
    result = []
    permute(nums, [], [False] * len(nums), result)
    return result


for p in all_permutations([1, 2, 3]):
    print(p)

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

// current holds the arrangement so far, used marks taken numbers
function permute(nums, current, used, result) {
  if (current.length === nums.length) {   // arrangement is full
    result.push([...current]);            // store a copy
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;                // skip numbers already placed
    used[i] = true;                       // mark used
    current.push(nums[i]);
    permute(nums, current, used, result); // fill next slot
    current.pop();                        // undo the choice (backtrack)
    used[i] = false;
  }
}

function allPermutations(nums) {
  const result = [];
  permute(nums, [], new Array(nums.length).fill(false), result);
  return result;
}

for (const p of allPermutations([1, 2, 3])) {
  console.log(`[${p.join(", ")}]`);
}

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

⏱️ How Slow Is This?

Permutations grow very fast. For a list of n items, the number of orderings is n factorial, written n!. That means 1 * 2 * 3 * ... * n.

See how quickly it climbs.

So with just 10 items you already have over three million orderings. There is no way around this. If you must list every ordering, you must produce that many.

Here is the cost in one place.

⚠️ Common Mistakes

A few slip-ups trip up most students. Watch for these.

• Forgetting the undo step. You must remove the number from current and set its flag back to false after recursing.
• Storing the same list instead of a copy. In Python and JavaScript you must store current[:] or [...current], not current itself. Otherwise every saved result points to the same list, which keeps changing.
• Checking the wrong flag, or never checking used at all. Skip this check and the same number repeats inside one arrangement.
• Recording the arrangement at the wrong time. Record only when current is full, not on every step.

🧩 What You’ve Learned

✅ A permutation is one ordering of all items, and a set of n items has n! orderings.

✅ Backtracking builds each arrangement one position at a time, then undoes a choice to try the next.

✅ A used array of flags stops a number from appearing twice in the same arrangement.

✅ You always record a copy of the arrangement, never the live list.

✅ The cost is O(n! * n), so this only works for small inputs.

🚀 What’s Next?

• Generate Subsets
• Introduction to Backtracking