Bidirectional search techniques optimize exhaustive searches by simultaneously exploring from both the initial state and target state, or by splitting the search space into manageable halves. These approaches significantly reduce the branching factor and memory requirements compared to unidirectional methods.

Bidirectional BFS for Shortest Path

Standard breadth-first search expands outward from a single source until reaching the destination. Bidirectional BFS initiates two concurrent searches—one from the start node and one from the end node. At each iteration, the algorithm expands the frontier with fewer nodes, minimizing the total number of explored states. The process terminates when the frontiers intersect.

Consider the word transformation problem where each step changes exactly one character. The following implementation uses two hash sets to track active frontiers and alternates expansion based on set cardinality:

class Solution {
public:
    int ladderLength(string startWord, string targetWord, vector<string>& wordPool) {
        unordered_set<string> dictionary(wordPool.begin(), wordPool.end());
        if (!dictionary.count(targetWord)) return 0;
        
        unordered_set<string> beginFrontier, endFrontier, tempFrontier;
        beginFrontier.insert(startWord);
        endFrontier.insert(targetWord);
        int transformations = 2;
        
        while (!beginFrontier.empty()) {
            for (const string& current : beginFrontier) {
                string candidate = current;
                for (int pos = 0; pos < candidate.length(); ++pos) {
                    char original = candidate[pos];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == original) continue;
                        candidate[pos] = c;
                        
                        if (endFrontier.count(candidate)) 
                            return transformations;
                        
                        if (dictionary.count(candidate)) {
                            tempFrontier.insert(candidate);
                            dictionary.erase(candidate);
                        }
                    }
                    candidate[pos] = original;
                }
            }
            
            transformations++;
            if (tempFrontier.size() <= endFrontier.size()) {
                beginFrontier = move(tempFrontier);
            } else {
                beginFrontier = endFrontier;
                endFrontier = move(tempFrontier);
            }
            tempFrontier.clear();
        }
        return 0;
    }
};

Meet-in-the-Middle for Exponential Spaces

When the search space grows exponentially (O(2^n)) and dynamic programming is infeasible due to large weight constraints, the meet-in-the-middle technique divides the problem set into two subsets of approximately equal size. Each subset generates all possible partial solutions (O(2^(n/2))), which are then combined to form complete answers.

Subset Sum with Constraints

For problems requiring subset enumeration with 40 elements, brute-force DFS examining 2^40 states exceeds computational limits. Splitting the array into two 20-element segments yields two sets of 2^20 combinations, which remains tractable. The solution merges these partial results using two-pointer or binary search techniques.

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

const int MAX_STATES = 1 << 20;
vector<long long> sequence(41);

int enumerate(int idx, int boundary, long long currentSum, long long limit, 
              vector<long long>& accumulator, int writePos) {
    if (currentSum > limit) return writePos;
    if (idx == boundary) {
        accumulator[writePos++] = currentSum;
        return writePos;
    }
    writePos = enumerate(idx + 1, boundary, currentSum, limit, accumulator, writePos);
    writePos = enumerate(idx + 1, boundary, currentSum + sequence[idx], limit, accumulator, writePos);
    return writePos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long maxWeight;
    cin >> n >> maxWeight;
    
    for (int i = 0; i < n; ++i) cin >> sequence[i];
    
    vector<long long> leftSums(MAX_STATES), rightSums(MAX_STATES);
    int leftCount = enumerate(0, n / 2, 0, maxWeight, leftSums, 0);
    int rightCount = enumerate(n / 2, n, 0, maxWeight, rightSums, 0);
    
    sort(leftSums.begin(), leftSums.begin() + leftCount);
    sort(rightSums.begin(), rightSums.begin() + rightCount);
    
    long long validCombinations = 0;
    int rightPtr = 0;
    
    for (int i = leftCount - 1; i >= 0; --i) {
        while (rightPtr < rightCount && leftSums[i] + rightSums[rightPtr] <= maxWeight)
            ++rightPtr;
        validCombinations += rightPtr;
    }
    
    cout << validCombinations;
    return 0;
}

Optimized Subsequence Sum with Duplicates

When the input contains duplicate values, the enumeration process can compress consecutive identical elements to reduce redundant states. Rather than binary choices (include/exclude) for every element, the algorithm considers including 0, 1, ..., k copies of each distinct value group.

class Solution {
public:
    static const int MAX_STATES = 1 << 20;
    
    int generateSums(int start, int end, long long runningTotal, int writeIdx,
                     vector<int>& arr, vector<long>& storage) {
        if (start == end) {
            storage[writeIdx++] = runningTotal;
            return writeIdx;
        }
        
        int nextDistinct = start + 1;
        while (nextDistinct < end && arr[nextDistinct] == arr[start])
            ++nextDistinct;
        
        int count = nextDistinct - start;
        for (int k = 0; k <= count; ++k) {
            writeIdx = generateSums(nextDistinct, end, 
                                   runningTotal + k * arr[start], 
                                   writeIdx, arr, storage);
        }
        return writeIdx;
    }
    
    int minAbsDifference(vector<int>& nums, int target) {
        vector<long> leftSums(MAX_STATES), rightSums(MAX_STATES);
        sort(nums.begin(), nums.end());
        
        int n = nums.size();
        int leftSize = generateSums(0, n / 2, 0, 0, nums, leftSums);
        int rightSize = generateSums(n / 2, n, 0, 0, nums, rightSums);
        
        sort(leftSums.begin(), leftSums.begin() + leftSize);
        sort(rightSums.begin(), rightSums.begin() + rightSize);
        
        int minDeviation = abs(target);
        int rightPtr = rightSize - 1;
        
        for (int i = 0; i < leftSize; ++i) {
            while (rightPtr > 0 && abs(leftSums[i] + rightSums[rightPtr - 1] - target) 
                   <= abs(leftSums[i] + rightSums[rightPtr] - target))
                --rightPtr;
            minDeviation = min(minDeviation, 
                             static_cast<int>(abs(leftSums[i] + rightSums[rightPtr] - target)));
        }
        return minDeviation;
    }
};

The bidirectional approach reduces time complexity from O(2^n) to O(2^(n/2)) for exponential problems and cuts the search frontier from O(b^d) to O(b^(d/2)) for graph traversal, where b is the branching factor and d is the solution depth.