DEV Community

Richie
Richie

Posted on

Generating Stack Permutations: A Recursive Thinking Process

#algorithms #cpp

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:

  1. Pop from stack (if not empty)
  2. 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...
}
Enter fullscreen mode Exit fullscreen mode

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] ✓
Enter fullscreen mode Exit fullscreen mode

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] ✓
Enter fullscreen mode Exit fullscreen mode

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
    }
}
Enter fullscreen mode Exit fullscreen mode

Key Observations

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

Thinking Process Summary

  1. Identify the decision points (push vs pop)
  2. Define the recursive state
  3. Handle base case (complete output)
  4. Explore both choices with backtracking
  5. 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.

Top comments (0)