递归＋回溯

返回条件

当前遍历完了整个原始数组，并且存留栈为空

if (index == input.size() && s.empty()) {
    for (int i = 0; i < output.size(); i++) {
        cout << output[i] << " ";
    }
    cout << endl;
    return;
}

递归

当存留栈不为空时，就可以开始输出元素

if (!s.empty()) {
    int top = s.top();
    s.pop();
    output.push_back(top);
    generateSequences(input, output, s, index);
    output.pop_back();
    s.push(top);
}

如果存留栈为空，就可以压入下一个元素

if (index < input.size()) {
    s.push(input[index]);
    generateSequences(input, output, s, index + 1);
    s.pop();  // 回溯
}

整个递归函数

当原始数组遍历完（使用下标来判断）并且此时栈为空，那么就可以输出一个结果。
当还没有遍历完，且栈不为空，就可以将结果弹出到输出数组里面留存。
当栈为空，且原始数组没有遍历完，当前元素之前的所有情况已经存储，可以向后添加元素准备下一个结果了

void generateSequences(vector<int>& input, vector<int>& output, stack<int>& s, int index) {
    if (index == input.size() && s.empty()) {
        for (int i = 0; i < output.size(); i++) {
            cout << output[i] << " ";
        }
        cout << endl;
        return;
    }

    if (!s.empty()) {
        int top = s.top();
        s.pop();
        output.push_back(top);
        generateSequences(input, output, s, index);
        output.pop_back();
        s.push(top);
    }

    if (index < input.size()) {
        s.push(input[index]);
        generateSequences(input, output, s, index + 1);
        s.pop(); 
    }
}

判断一个数组是不是出栈数组

nums为我们输入的1-n构成的1，2，...., n数组
curnums则是我们需要判断的数组
原理：利用stack去存储nums的数据，每次存储判断当前top是否与curnums的当前下标相同，如果相同，则pop，然后移动curnums的下标，直到遍历完整个数组
如果curnums是一个合理的出栈数组，那么最后这个栈应该为空，因为s模拟的就是元素入栈出栈的过程。

bool isValidPopSequence(vector<int>& nums, vector<int>& curnums) {
    stack<int> s;
    int j = 0;

    // 遍历每个入栈元素
    for (int i = 0; i < nums.size(); ++i) {
        s.push(nums[i]);
        // 检查栈顶元素是否和出栈序列中的下一个元素相同
        while (!s.empty() && s.top() == curnums[j]) {
            s.pop();
            ++j;  // 移动到下一个要匹配的出栈元素
        }
    }

    // 如果所有元素都能成功匹配，则是一个有效的出栈序列
    return s.empty();
}