State Space Search / Exhaustive Search

Concept

Exhaustive search (brute force with backtracking) systematically explores all possible states. Generate all permutations, subsets, or combinations and check each one. Backtracking prunes branches early when a partial solution can't lead to a valid answer, making it faster than pure brute force.

When to Use

  • ▸Generating all permutations of n elements (n <= 10)
  • ▸Generating all subsets of a set (n <= 20)
  • ▸N-Queens, Sudoku solver, maze solving
  • ▸Any problem with small constraints where you must try all possibilities
  • ▸When no polynomial-time algorithm exists (NP-hard problems with small n)

Intuition

Think of it as exploring a decision tree. At each step you make a choice (pick an element, place a queen, etc.), go deeper, then undo the choice and try the next option. It's like trying every combination on a lock, but smarter — if the first two digits are already wrong, skip all combinations starting with them. The 'undo' step (backtrack) is what makes it memory-efficient compared to generating everything upfront.

Complexity

Time
O(n!) for permutations, O(2^n) for subsets
Space
O(n) recursion stack

Template Code

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

// --- Generate All Permutations ---
void permute(vector<int> &v, int idx){
    if(idx == v.size()){
        for(int x : v) cout << x << " ";
        cout << "\n";
        return;
    }

    for(int i = idx; i < v.size(); i++){
        swap(v[idx], v[i]);
        permute(v, idx+1);
        swap(v[idx], v[i]);  // backtrack
    }
}

// --- Generate All Subsets (Bitmask) ---
void subsets(vector<int> &v){
    int n = v.size();
    for(int mask = 0; mask < (1 << n); mask++){
        cout << "{ ";
        for(int i = 0; i < n; i++){
            if(mask & (1 << i)) cout << v[i] << " ";
        }
        cout << "}\n";
    }
}

// --- Backtracking Template ---
int n, ans = 0;
vector<bool> visited;

void solve(int depth){
    if(depth == n){
        ans++;
        return;
    }

    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        // add pruning conditions here

        visited[i] = true;
        solve(depth+1);
        visited[i] = false;  // backtrack
    }
}

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

    cin >> n;

    // Permutations
    vector<int> v(n);
    for(int i = 0; i < n; i++) v[i] = i+1;
    permute(v, 0);

    cout << "---\n";

    // Subsets
    subsets(v);

    cout << "---\n";

    // Backtracking count
    visited.assign(n, false);
    solve(0);
    cout << ans << " permutations\n";

    return 0;
}

// Sample Input:
// 3
//
// Sample Output:
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 2 1
// 3 1 2
// ---
// { }
// { 1 }
// { 2 }
// { 1 2 }
// { 3 }
// { 1 3 }
// { 2 3 }
// { 1 2 3 }
// ---
// 6 permutations