🌳 Structural Recursion for NP Tasks: The Art of Brute Force

📄 Abstract

When solving NP tasks (problems where no polynomial-time solution is known), we cannot rely on direct formulas or simple loops. Instead, we must explore the entire "universe" of possibilities. This document redefines recursion as a Decision Engine, evolving from simple iteration to State Space Exploration.

1. 🧠 The Core Philosophy & Logic

Structural Recursion is the framework used to solve NP decision tasks. Since these tasks often rely on brute force to find a "Yes/No" or a specific configuration, the goal is to organize this brute force intelligently.

The "State" (Entity)

A DP or Recursive state represents an entity at a specific moment. According to Navneeet Hingankar, this entity is fundamentally a tracker of changes. It can be represented as:

Range
Set
Pair
Compressed Mask

The Universal Logic

Regardless of the representation, the logic always follows this flow: $$\text{Base Condition} \to \text{Change} \to \text{Recurse} \to \text{Merge}$$

Visualization

While mathematical recurrence relations are precise, visualizing the Decision Tree is often far more effective for understanding how the recursion "unfolds."

2. 📊 Complexity Analysis & Optimization

There is a critical distinction in complexity depending on what you are calculating.

A. Generating Full Subsets: O(2^N * N)

Why? There are $2^N$ subsets. To store or print them, you must iterate through the elements of each subset (average length $N/2$).
Insight: The extra $N$ comes from the copy/print operations at the leaf nodes or during iterative merging steps.

B. Subset Sum Optimization: O(2^N)

Why? If you only need to know if a sum exists (or count them), you do not need to store the vector of elements.
Optimization: By passing currentSum as a simple integer, the work per node becomes $O(1)$. The total work is simply the number of nodes in the tree ($2^{N+1}$).

3. 📘 Handbook: Patterns of Exploration

A. Combination Tasks: Subset Generation

Use Case: Tasks where order does not matter (e.g., $\{A, B\} \equiv \{B, A\}$).

The "Choose, Recurse, Undo" Template

Mathematically, this involves iterating through a stream of $N$ elements and making a binary choice for each: Pick or Skip. For complex data structures, we cannot afford to copy the structure for every recursive call. Instead, we use a Backtracking Template that modifies a single global structure.

Choose: Modify the global state (add element).
Recurse: Move to the next index.
Undo: Revert the change (remove element) to restore the state for the sibling branch.

Click to expand C++ Template: Subset Generation

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

// Global variables are preferred here to mimic stack memory access 
// and avoid passing heavy objects by value.
int n;
vector<int> arr;
vector<int> currentSubset; 

void generateSubsets(int index) {
    // [Base Condition]: We have processed all elements
    if (index == n) {
        cout << "{ ";
        for (int x : currentSubset) cout << x << " ";
        cout << "}\n";
        return;
    }

    // --- CHOICE 1: PICK the element ---
    currentSubset.push_back(arr[index]); // DO (Choose)
    generateSubsets(index + 1);          // RECURSE
    currentSubset.pop_back();            // UNDO (Backtrack) -> Crucial for state restoration

    // --- CHOICE 2: SKIP the element ---
    // No change to data structure needed here
    generateSubsets(index + 1);          // RECURSE
}

int main() {
    arr = {1, 2, 3};
    n = arr.size();
    generateSubsets(0);
    return 0;
}

Optimization: Pruning

If asking "Does a subset sum to $K$?", we can optimize further. If currentSum > K (and numbers are positive), we Prune (cut off) that branch immediately.

Click to expand C++ Template: Optimized Subset Sum

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

int n;
vector<int> arr;
int target = 10;
int solutionCount = 0;

void subsetSum(int index, int currentSum) {
    // [Pruning]: If sum exceeds target, stop this branch.
    // Effectively reduces search space.
    if (currentSum > target) return; 

    // [Base Condition]
    if (index == n) {
        if (currentSum == target) solutionCount++;
        return;
    }

    // Note: We pass the sum by value, so "Undo" is implicit (stack frame clears).

    // Choice 1: Pick
    subsetSum(index + 1, currentSum + arr[index]); 

    // Choice 2: Skip
    subsetSum(index + 1, currentSum);
}

B. Permutation Tasks: N-Queens & Slot Filling

Use Case: Tasks where order matters (e.g., $[A, B] \neq [B, A]$).

1. Simplification via ID Generation (Linearization)

Handling 2D grids (rows/cols) in recursion can be complex. A key technique introduced is Linearizing the Multi-Dimensional Space. Instead of recursing on (row, col), we recurse on a single integer ID.

Formula: $ID = (row \times MaxCol) + col$
Reverse: $row = ID / MaxCol$, $col = ID \% MaxCol$
Benefit: This turns a 2D grid search into a simple linear recursion (ID to ID + 1), guaranteeing a Directed Acyclic Graph (DAG) structure with no cycles.

Click to expand C++ Template: N-Queens using ID Linearization

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

int N;
int board[20][20]; // Global variable for easy access

// Helper to check safety (Column, Row, Diagonals)
bool isSafe(int r, int c) {
    for (int i = 0; i < N; i++) {
        if (board[r][i]) return false; // Check Row
        if (board[i][c]) return false; // Check Col
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] && abs(r - i) == abs(c - j)) return false; // Check Diagonals
        }
    }
    return true;
}

// Recursion using purely ID + 1 logic
void solveNQueens(int cellID, int queensPlaced) {
    // [Base Case 1]: Success
    if (queensPlaced == N) {
        cout << "Solution Found!\n";
        return;
    }

    // [Base Case 2]: Failure (ID out of bounds)
    if (cellID == N * N) return;

    // Decode ID -> 2D Coordinates
    int row = cellID / N;
    int col = cellID % N;

    // --- CHOICE 1: Place Queen (if safe) ---
    if (isSafe(row, col)) {
        board[row][col] = 1;                        // DO
        solveNQueens(cellID + 1, queensPlaced + 1); // RECURSE
        board[row][col] = 0;                        // UNDO
    }

    // --- CHOICE 2: Skip this cell ---
    // Essential to allow queens to be placed in later columns/rows
    solveNQueens(cellID + 1, queensPlaced);
}

int main() {
    N = 4;
    solveNQueens(0, 0);
    return 0;
}

2. Generating Permutations: Two Methods

Sequential Slot Filling (Factorial): Create empty slots and fill them one by one with available numbers. (Standard approach).
Gap Insertion (Structural): Start with a sequence. Place the next element into the gaps created by previous elements.
- Example: If you have [1], the next element 2 can go before 1 ([2,1]) or after 1 ([1,2]). This is trickier to implement but useful for complex structural constraints.

C. Grid Exploration (Pathfinding)

Use Case: Searching for a specific path or pattern within a 2D matrix (e.g., Word Search). Difference: Unlike flood-fill, these tasks often require backtracking—marking a cell as visited for the current path only.

Click to expand C++ Template: Word Search

bool dfs(vector<vector<char>>& board, string& word, int r, int c, int idx) {
    // Base Case: We found all characters
    if (idx == word.size()) return true;

    // Boundary & Validity Checks
    if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size() || board[r][c] != word[idx])
        return false;

    // Action: Mark as visited (temporarily mangle the board)
    char temp = board[r][c];
    board[r][c] = '#';

    // Recursive Step: Try all 4 directions
    bool found = dfs(board, word, r+1, c, idx+1) ||
                 dfs(board, word, r-1, c, idx+1) ||
                 dfs(board, word, r, c+1, idx+1) ||
                 dfs(board, word, r, c-1, idx+1);

    // Backtrack: Restore the character
    board[r][c] = temp;

    return found;
}

D. Constrained Growth

Use Case: Generating valid structures where next steps depend on previous counts (e.g., Generate Parentheses). Structure: Iterate over abstract choices (e.g., "Add Open" vs "Add Close").

Click to expand C++ Template: Generate Parentheses

void generate(int n, int open, int close, string current, vector<string>& result) {
    if (current.length() == n * 2) {
        result.push_back(current);
        return;
    }
    if (open < n)      generate(n, open + 1, close, current + "(", result);
    if (close < open)  generate(n, open, close + 1, current + ")", result);
}

E. The "Complex State" Pattern (History)

Use Case: When the decision depends on more than just the current index, requiring "history" in arguments (e.g., Expression Add Operators).

Click to expand C++ Template: Expression Add Operators

void addOperators(int index, long currentVal, long lastOperand, string expression, const string& num, int target) {
    if (index == num.size()) {
        if (currentVal == target) cout << expression << endl;
        return;
    }

    for (int i = index; i < num.size(); i++) {
        if (i > index && num[index] == '0') break; // No leading zeros
        string part = num.substr(index, i - index + 1);
        long val = stol(part);

        if (index == 0) {
            addOperators(i + 1, val, val, part, num, target);
        } else {
            addOperators(i + 1, currentVal + val, val, expression + "+" + part, num, target);
            addOperators(i + 1, currentVal - val, -val, expression + "-" + part, num, target);
            // Multiplication requires reverting the last operand
            addOperators(i + 1, (currentVal - lastOperand) + (lastOperand * val), lastOperand * val, expression + "*" + part, num, target);
        }
    }
}

4. 🧩 Summary Table: Which Pattern to Use?

Pattern	Logic	Structural Concept	Classic Example
Pick/Skip	Binary Tree ($2^N$)	Subset Generation	Subset Sum / Knapsack
Slot Filling	N-ary Tree ($N!$)	Permutations / ID Linearization	N-Queens
Constrained Growth	Abstract Choice	Valid State Expansion	Generate Parentheses
Parsing	Variable Branching	History Tracking	Expression Add Operators

5. 📝 Check Your Understanding

Ready to test your brute force skills on classic NP problems? 👉 Take the NP Tasks Quiz

Pattern	Logic	Structural Concept	Classic Example
Pick/Skip	Binary Tree (\(2^N\))	Subset Generation	Subset Sum / Knapsack
Slot Filling	N-ary Tree (\(N!\))	Permutations / ID Linearization	N-Queens
Constrained Growth	Abstract Choice	Valid State Expansion	Generate Parentheses
Parsing	Variable Branching	History Tracking	Expression Add Operators