Backtracking: Try, and Undo

Explore every possibility, neatly

Backtracking builds an answer one choice at a time. After exploring everything that follows a choice, it undoes it and tries the next. The pattern: choose → explore → un-choose.

Think of it like this: Trying a combination lock digit by digit: fix the first digit, try everything for the rest, then change the first digit.

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

string items = "abc";
string current;

void subsets(int i) {
    if (i == (int)items.size()) {
        cout << "{" << current << "} ";
        return;
    }
    current.push_back(items[i]);   // choose: take items[i]
    subsets(i + 1);
    current.pop_back();            // un-choose
    subsets(i + 1);                // skip items[i]
}

vector<bool> used(3, false);

void permutations() {
    if (current.size() == items.size()) {
        cout << current << ' ';
        return;
    }
    for (int i = 0; i < (int)items.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.push_back(items[i]);
        permutations();
        current.pop_back();
        used[i] = false;
    }
}

int main() {
    subsets(0);
    cout << endl;
    permutations();
    cout << endl;
    return 0;
}

Output

{abc} {ab} {ac} {a} {bc} {b} {c} {} 
abc acb bac bca cab cba 

Subsets: 2ⁿ of them, O(2ⁿ). Permutations: n! of them, O(n!).

Tip: C++ also has next_permutation in <algorithm> to step through permutations in sorted order.