Generating Stack Permutations: A Recursive Thinking Process

Richie — Sat, 27 Sep 2025 09:20:24 +0000

Problem Understanding

Given numbers 1, 2, 3, ..., n that must be pushed onto a stack in order, generate all possible output sequences from interleaved push/pop operations.

Key Constraint: Push order is fixed, but pop timing is flexible.

Core Insight: Decision Tree Approach

At any point during the process, you have exactly two choices:

Pop from stack (if not empty)
Push next number (if available)

This creates a binary decision tree where each path represents a valid sequence.

Recursive State Definition

The recursive function tracks three pieces of state:

nextPush: next number to push (1 to n)
stack: current stack contents
output: numbers popped so far

void generate(int nextPush, stack<int>& stk, vector<int>& output) {
    if (output.size() == n) {
        // Base case: complete sequence found
        print(output);
        return;
    }

    // Two recursive choices...
}

Step-by-Step Execution for n=2

Initial State: nextPush=1, stack=[], output=[]

Path 1: Push then Pop

Push 1 → stack=[1], nextPush=2
Push 2 → stack=[1,2], nextPush=3  
Pop 2 → stack=[1], output=[2]
Pop 1 → stack=[], output=[2,1] ✓

Path 2: Interleaved Push/Pop

Push 1 → stack=[1], nextPush=2
Pop 1 → stack=[], output=[1]
Push 2 → stack=[2], nextPush=3
Pop 2 → stack=[], output=[1,2] ✓

Backtracking Implementation

void dfs(int n, int index, stack<int>& stk, vector<int>& path) {
    if (path.size() == n) {
        for (int num : path) cout << num;
        cout << endl;
        return;
    }

    // Choice 1: Pop from stack
    if (!stk.empty()) {
        int top_val = stk.top();
        stk.pop();
        path.push_back(top_val);

        dfs(n, index, stk, path);

        path.pop_back();  // Backtrack
        stk.push(top_val);
    }

    // Choice 2: Push next number
    if (index <= n) {
        stk.push(index);
        dfs(n, index + 1, stk, path);
        stk.pop();  // Backtrack
    }
}

Key Observations

Catalan Numbers: The number of valid sequences equals the nth Catalan number
Parentheses Connection: Push = '(', Pop = ')' - valid sequences correspond to balanced parentheses
Tree Traversal: Similar to generating all possible binary tree traversals

Thinking Process Summary

Identify the decision points (push vs pop)
Define the recursive state
Handle base case (complete output)
Explore both choices with backtracking
Recognize the combinatorial pattern

This approach transforms a complex combinatorial problem into a systematic exploration of a decision tree, demonstrating how recursive thinking can simplify seemingly difficult problems.

DEV Community: Richie