How to Generate All Permutations with Backtracking: A Step‑by‑Step Guide

Permutation generation via backtracking

To list all permutations of an array such as [1, 2, 3], fix each possible first element, then recursively fix the second, and finally the third, producing six orders. This can be visualized as a tree where each node is a partial permutation; a depth‑first search (DFS) from the root to each leaf yields one full permutation.

Why DFS

Simple to implement.

Uses a single global state variable, avoiding extra memory.

State transitions are straightforward, making backtracking easy.

Recursive structure

Each non‑leaf node chooses the next element from the remaining pool. Recursion stops when the permutation is complete. Two state variables are needed:

A list (or the current prefix) of already chosen elements.

A boolean array used (initially false) indicating whether each element has been selected, giving O(1) duplicate checks.

Backtracking

After returning from a deeper recursive call, the previous state must be restored (undo the last swap) so that subsequent branches start from the correct configuration.

Complete C implementation

#include <stdio.h>
static int count = 0;

void swap(char *str, int a, int b) {
    char tmp = str[a];
    str[a] = str[b];
    str[b] = tmp;
}

/* Return 1 if str[k] has not appeared between begin and k‑1 */
int isSwapped(char *str, int begin, int k) {
    for (int i = begin; i < k; ++i) {
        if (str[i] == str[k]) {
            return 0;
        }
    }
    return 1;
}

/* Generate all permutations of str[begin..end] */
void full_permutation(char *str, int begin, int end) {
    if (begin == end) {
        count++;               /* a leaf – one permutation */
        return;
    }
    for (int i = begin; i <= end; ++i) {
        if (!isSwapped(str, begin, i)) {
            continue;          /* skip duplicates */
        }
        swap(str, begin, i);                /* fix element at position begin */
        full_permutation(str, begin + 1, end); /* recurse */
        swap(str, begin, i);                /* undo swap (backtrack) */
    }
}

Python backtracking template

result = []

def backtrack(path, choices):
    if end_condition:
        result.append(path)
        return
    for choice in choices:
        # make a choice
        backtrack(path + [choice], new_choices)
        # undo the choice (implicitly by returning)