Permutation (Generate All)

Concept

Generate all permutations of n elements. Two common approaches: (1) Use C++ STL next_permutation on a sorted array to iterate through all n! permutations. Simple and contest-friendly. (2) Recursive backtracking — pick each unused element, recurse, then undo the pick. More flexible, works when you need to prune or customize the generation.

When to Use

  • ▸Brute-force / exhaustive search over all orderings
  • ▸Checking all possible arrangements (e.g., assigning tasks to people)
  • ▸Problems with n ≤ 8-10 where O(n!) is feasible
  • ▸Backtracking problems that need pruning

Intuition

(next_permutation) Think of permutations as numbers in lexicographic order — next_permutation finds the next number each time by flipping the smallest suffix. (backtracking) Build the permutation slot by slot. At each slot, try every unused element. If something doesn't work, undo and try the next — like filling in a sudoku.

Complexity

Time
O(n! × n)
Space
O(n)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

// ===== Version 1: next_permutation (STL) =====

// int main(){
//     ios_base::sync_with_stdio(0), cin.tie(0);
//
//     int n;
//     cin >> n;
//
//     vector<int> a(n);
//     for(int i = 0; i < n; i++) cin >> a[i];
//
//     sort(a.begin(), a.end());
//
//     do{
//         for(int i = 0; i < n; i++){
//             cout << a[i];
//             if(i < n-1) cout << " ";
//         }
//         cout << "\n";
//     }while(next_permutation(a.begin(), a.end()));
//
//     return 0;
// }

// ===== Version 2: Recursive backtracking =====

int n;
vector<int> a, perm;
vector<bool> visited;

void gen(int idx){
    if(idx == n){
        for(int i = 0; i < n; i++){
            cout << perm[i];
            if(i < n-1) cout << " ";
        }
        cout << "\n";
        return;
    }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            visited[i] = true;
            perm[idx] = a[i];
            gen(idx+1);
            visited[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    a.resize(n);
    perm.resize(n);
    visited.assign(n, false);
    for(int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());
    gen(0);

    return 0;
}

// Sample Input:
// 3
// 1 2 3
//
// Sample Output:
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1