Backtracking: Generating All Subsets & Permutations

1. Algorithm & Complexity

Backtracking lets us build up a solution step by step and “undo” choices when they lead to dead ends. We can use it both to generate all subsets (the power set) and all permutations of an array of size n.

  • Subsets (power set): at each index i, decide to include or exclude element a[i].
  • Permutations: build a sequence by picking any unused element at each position.

Time Complexity

  • Subsets: There are 2n subsets, and printing each takes up to O(n), so O(n·2n).
  • Permutations: There are n! permutations, each printed in O(n), so O(n·n!).

Memory Complexity

We store one partial solution of size ≤n plus a recursion stack of depth ≤n. Total extra memory: O(n).

2. Two Easy Codeforces-Style Problems

2.1 – Codeforces “Power Set” (n≤16)

Task: Given n (≤16) and an array of n distinct integers, print all its subsets. 

Input:
3
1 2 3

Output:
[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

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

int n;
vector<int> a, curr;

void dfs(int idx) {
    if (idx == n) {
        cout << "[";
        for (int i = 0; i < curr.size(); ++i) {
            if (i) cout << ",";
            cout << curr[i];
        }
        cout << "]\n";
        return;
    }
    // Exclude a[idx]
    dfs(idx + 1);
    // Include a[idx]
    curr.push_back(a[idx]);
    dfs(idx + 1);
    curr.pop_back();
}

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    dfs(0);
    return 0;
}

2.2 – Codeforces “All Permutations” (n≤8)

Task: Given n (≤8), print all permutations of numbers 1…n. 

Input:
3

Output:
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;

int n;
vector<int> perm;
vector<bool> used;

void dfs() {
    if (perm.size() == n) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        used[i] = true;
        perm.push_back(i);
        dfs();
        perm.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> n;
    perm.reserve(n);
    used.assign(n+1, false);
    dfs();
    return 0;
}

3. Two Intermediate Problems

3.1 – Codeforces “Subset Sum Equals Target” (n≤20)

Task: Given n (≤20), array a[i] and target S (≤109), count subsets whose sum = S. 

Input:
5 5
1 2 3 2 1

Output:
3

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

int n;
long long S, ans = 0;
vector<long long> a;

void dfs(int idx, long long sum) {
    if (idx == n) {
        if (sum == S) ans++;
        return;
    }
    // exclude
    dfs(idx + 1, sum);
    // include
    dfs(idx + 1, sum + a[idx]);
}

int main() {
    cin >> n >> S;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    dfs(0, 0);
    cout << ans << '\n';
    return 0;
}

3.2 – Codeforces “Next Permutation Rank” (n≤10)

Task: Given a permutation of 1…n (≤10), find its 1-based index in lexicographic order. 

Input:
3
2 3 1

Output:
4

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

int n;
vector<int> p;
long long fact[21];

int main() {
    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i;
    long long rank = 1;
    vector<bool> used(n+1,false);
    for (int i = 0; i < n; ++i) {
        int smaller = 0;
        for (int x = 1; x < p[i]; ++x)
            if (!used[x]) smaller++;
        rank += smaller * fact[n-1-i];
        used[p[i]] = true;
    }
    cout << rank << '\n';
    return 0;
}

4. One Hard Problem

4.1 – Codeforces “Hamiltonian Path Count” (n≤10)

Task: Given n (≤10) and an undirected graph via adjacency matrix, count all Hamiltonian paths visiting each vertex exactly once. 

Input:
4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Output:
14

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

int n, ans = 0;
vector<vector<int>> adj;
vector<bool> used;

void dfs(int u, int visited) {
    if (visited == (1<<n) - 1) {
        ans++;
        return;
    }
    for (int v = 0; v < n; ++v) {
        if (!used[v] && adj[u][v]) {
            used[v] = true;
            dfs(v, visited | (1<<v));
            used[v] = false;
        }
    }
}

int main() {
    cin >> n;
    adj.assign(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> adj[i][j];
    // start from each vertex
    for (int i = 0; i < n; ++i) {
        used.assign(n,false);
        used[i] = true;
        dfs(i, 1<<i);
    }
    cout << ans << '\n';
    return 0;
}

All these problems share the same backtracking blueprint:

  • Choose … recurse … undo choice.
  • Keep a small “used” or “current” array to track state.