Hard · recursion

All Permutations

A permutation starts with a choice: which number goes first? Fix it, and what remains is the same problem one size smaller. Recursion writes that sentence literally — choose, delegate, un-choose.

At a glanceRecurse over positions: for each unused value v, place v, mark it used, recurse for the next position, then unmark. Trying values in increasing order gives lexicographic order for free.

Problem

Input: One integer n (1 ≤ n ≤ 6).

Output: All n! permutations of 1..n, one per line, values separated by single spaces, in lexicographic order.

Samples:

Input	Output
`3`	`1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1`

n ≤ 6 because 7! = 5040 lines and 10! = 3.6 million — factorial growth is the whole lesson here. The recursion depth is only n; the explosion is in the branching.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Write the base case first

When pos == n the array perm is full: print it with single spaces and a newline, then return. Every recursion needs a smallest case that stops the descent — write it before the loop, or the function has nothing to stand on.

Hint 2 — The loop IS the branching

At position pos, loop value from 1 to n. Skip values already marked in used. Otherwise: perm[pos] = value; used[value] = 1; generate(pos + 1); — and then the step beginners forget: used[value] = 0; to give the value back. Trying values in increasing order makes lexicographic order free.

Hint 3 — Trust the recursion

After placing one value at pos, the call generate(pos + 1) must produce every completion of the current prefix, in order, and return. Do not trace it by hand past one level — the proof is structural: it is exactly the same problem, one size smaller.

Solution (try it first!)

#include <iostream>
using namespace std;

int n;
int used[10];
int perm[10];

void generate(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    for (int value = 1; value <= n; value++) {
        if (used[value]) continue;
        used[value] = 1;
        perm[pos] = value;
        generate(pos + 1);
        used[value] = 0;
    }
}

int main() {
    cin >> n;
    generate(0);
    return 0;
}

You have written your first backtracker: choose, recurse, un-choose. The identical skeleton solves subsets, N-queens, Sudoku and maze paths — only the loop body changes. To see recursion from its other side (the call stack, not the search tree), climb Tower of Hanoi.

Deep dive

Why this works

The search space is a tree: depth is the position, branches are the unused values. Backtracking walks that tree in lexicographic DFS order, and the un-mark step is what lets a value appear again in a different branch — without it, each value could be used once in the entire run.

The cost

O(n! × n) time — n! lines, n work to print each — and O(n) space for the recursion stack and the arrays. At n = 10 that is already 36 million lines: factorial growth outruns any optimization.

Where it goes wrong

Forgetting used[value] = 0; after the recursive call. With n = 2 you get one line instead of two; at n = 6 a handful instead of 720 — and the cause is a single missing line.
Printing inside the loop instead of at pos == n. You would emit every partial prefix, and the line count stops matching n! altogether.

Next step

Same skeleton, different payloads: subsets, N-queens, mazes. And the call-stack view of recursion is the star of Tower of Hanoi.

Two things to remember

Backtracking = choose, recurse, un-choose; the un-choose is not optional.
Loop values in increasing order and lexicographic order comes free.

🐞 This version fails — open it and try

Never gives the value back — used[value] = 0 is missing

#include <iostream>
using namespace std;

int n;
int used[10];
int perm[10];

void generate(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    for (int value = 1; value <= n; value++) {
        if (used[value]) continue;
        used[value] = 1;
        perm[pos] = value;
        generate(pos + 1);
    }
}

int main() {
    cin >> n;
    generate(0);
    return 0;
}