非递归实现组合型枚举

93. 递归实现组合型枚举 – AcWing题库

77. 组合 – 力扣（Leetcode）

递归

void dfs(int u, int cnt, int state) {
    // 1
    if (cnt > k || cnt + n - u + 1 < m) return;
    if (cnt == k) {
        for (int i = n; i >= 0; i--)
            if (state >> i & 1)
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    dfs(u + 1, cnt + 1, state | (1 << u));
    // 2
    dfs(u + 1, cnt, state);
    // 3
}

非递归

递归改写为非递归版本，本质上就是不使用由系统提供的提供的递归工作栈，而是人为的构造一个栈，然后switch认为的选择需要进行的代码片段，有助于对递归和栈的理解。

int n, k;
struct Node{
    int p, u, c, s;
};
void solve(int u, int cnt, int status){
    stack<Node> st;
    st.push({1, u, cnt, status});
    while(st.size()){
        auto t = st.top(); st.pop();
        if(t.p == 1){
            if(t.c > k || t.c + n - t.u < k)
                continue;
            if(t.c == k){
                for(int i = 0; i<n; i++){
                    if(t.s >> i & 1)
                        cout << i + 1 << " ";
                }
                cout << endl;
                continue;
            }
            t.p = 2;
            st.push(t); // 由于模拟递归，因此要保存下个待执行的代码片段
            st.push({1, t.u + 1, t.c + 1, t.s | (1 << t.u)}); // 进入递归，下个待执行的代码片段仍然是1
        } else if(t.p == 2){
            t.p = 3;
            st.push(t); // 下个待执行片段为3
            st.push({1, t.u + 1, t.c, t.s});
        } else if(t.p == 3)
            continue;
    }
}

int main(){
    cin >> n >> k;
    solve(0, 0, 0);
    return 0;
}