Complete Search

Algorithms Exhaustive Search

Complete search (also known as brute force) is a problem-solving technique that examines all possible solutions to find the correct answer. While not always the most efficient, it guarantees finding the optimal solution when implemented correctly.

When to Use Complete Search

Complete search is ideal when:

Good Candidates for Complete Search:

Small input size (typically n ≤ 20-25)
No obvious pattern or mathematical formula
All possible solutions must be examined
Time limit allows for exponential algorithms

Generating All Subsets

A subset is a collection of elements from a set. For a set of n elements, there are 2^n possible subsets:

Recursive Approach


void generateSubsets(vector<int>& nums, vector<int>& current, int index) {
    // Base case: we've considered all elements
    if (index == nums.size()) {
        // Print or process the current subset
        for (int x : current) {
            cout << x << " ";
        }
        cout << endl;
        return;
    }
    
    // Choice 1: Don't include nums[index]
    generateSubsets(nums, current, index + 1);
    
    // Choice 2: Include nums[index]
    current.push_back(nums[index]);
    generateSubsets(nums, current, index + 1);
    current.pop_back(); // Backtrack
}

// Usage
vector<int> nums = {1, 2, 3};
vector<int> current;
generateSubsets(nums, current, 0);

Bit Manipulation Approach


void generateSubsetsBit(vector<int>& nums) {
    int n = nums.size();
    
    // Iterate through all possible bitmasks
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        
        for (int i = 0; i < n; i++) {
            // Check if i-th bit is set
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }
        
        // Process subset
        for (int x : subset) {
            cout << x << " ";
        }
        cout << endl;
    }
}

Generating All Permutations

A permutation is an arrangement of elements. For n distinct elements, there are n! permutations:


void generatePermutations(vector<int>& nums, vector<bool>& used, vector<int>& current) {
    if (current.size() == nums.size()) {
        // We have a complete permutation
        for (int x : current) {
            cout << x << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (!used[i]) {
            // Choose nums[i]
            used[i] = true;
            current.push_back(nums[i]);
            
            // Recurse
            generatePermutations(nums, used, current);
            
            // Backtrack
            current.pop_back();
            used[i] = false;
        }
    }
}

// Using STL next_permutation (easier approach)
void generatePermutationsSTL(vector<int> nums) {
    sort(nums.begin(), nums.end());
    do {
        for (int x : nums) {
            cout << x << " ";
        }
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end()));
}

Backtracking Template

Backtracking is a systematic way to explore all possibilities:


void backtrack(State& current, vector<Solution>& solutions) {
    if (isComplete(current)) {
        solutions.push_back(current);
        return;
    }
    
    for (Choice choice : getPossibleChoices(current)) {
        if (isValid(current, choice)) {
            // Make the choice
            makeChoice(current, choice);
            
            // Recurse
            backtrack(current, solutions);
            
            // Undo the choice (backtrack)
            undoChoice(current, choice);
        }
    }
}

Example: N-Queens Problem

Place N queens on an N×N chessboard so that no two queens attack each other:


class NQueens {
    vector<vector<string>> solutions;
    vector<string> board;
    
public:
    vector<vector<string>> solveNQueens(int n) {
        board = vector<string>(n, string(n, '.'));
        backtrack(0, n);
        return solutions;
    }
    
private:
    void backtrack(int row, int n) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, n)) {
                board[row][col] = 'Q';
                backtrack(row + 1, n);
                board[row][col] = '.';
            }
        }
    }
    
    bool isValid(int row, int col, int n) {
        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        
        // Check diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        // Check anti-diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
};

Optimization Techniques

Make complete search faster with these techniques:

Pruning Strategies

Early termination: Stop exploring if current path can't lead to solution
Constraint checking: Validate constraints as early as possible
Ordering: Try most promising choices first
Memoization: Cache results of subproblems
Symmetry breaking: Avoid exploring symmetric states

Time Complexity Analysis

Complexity Warning

Subsets: O(2^n) - doubles with each new element
Permutations: O(n!) - grows extremely fast
General backtracking: Often exponential
Rule of thumb: Complete search is usually feasible only for n ≤ 20-25

owlingcode