题目

组合型枚举

本题解主要讲解非递归解法，也会顺便讲解递归解法作为基础，都配有代码，绝对良心，不良心不要钱。

解法1：递归

分析

很简单了，m位一个个枚举选什么直接就可以AC，注意3点：

1. 数码要按顺序；
2. 选的时候还要保证剩下足够的数码给以后选，避免出现无解的情况；
3. 好好琢磨递归初始值和结束条件。

喜闻乐见的C++代码

#include <bits/stdc++.h>


using namespace std;


int n, m;
int arr[30];


void dfs(int pos_arr, int last) {
    if (pos_arr > m) {
        for (int i = 1; i <= m; ++i) {
            printf("%d", arr[i]);
            putchar(i == m ? '\n' : ' ');
        }
        return;
    }
    for (int i = last + 1; i <= n - (m - pos_arr); ++i) {
        arr[pos_arr] = i;
        dfs(pos_arr + 1, i);
    }
}


int main(void) {
    scanf("%d%d", &n, &m);
    dfs(1, 0);
    return 0;
}

解法2：非递归

分析

已经有了递归解法作为铺垫，只要在其基础上进行优化即可。

首先，我们需要了解编译器在实现递归（也就是函数的调用）时的方法：使用一个栈。每当一个函数调用其它函数（或者它本身）时，会先将这个函数的信息制作成一个“栈帧”入“调用栈”，信息具体包括：

1. 函数的参数
2. 函数的局部变量
3. 函数执行到了哪里

在我们的程序中是这样的：

struct data_t {
    int pos_arr, last; // 两个参数
    int i; // 循环变量（局部变量）
};
struct pkg_t {
    int nxt; // 下一次要执行的位置
    data_t data;
};
stack<pkg_t> st; // 调用栈，直接使用了stl的stack，很方便

而整个函数不停调用的过程表现为一个循环，当栈空了（所有函数执行完了），程序结束：

while (!st.empty()) {
    pkg_t now_pkg = st.top();
    st.pop();
    int pos_arr = now_pkg.data.pos_arr,
        last = now_pkg.data.last,
        i = (now_pkg.data.i == UNDEF ? last + 1 : now_pkg.data.i); // UNDEF前面定义了，不会CE
    // ...
    NEXT_TURN: /* NOTHING */ ;
}

程序中被...标记的地方是函数的主体，和递归版本的函数基本一致。NEXT_TURN用于一个函数调用结束return，并回到栈里保存的以前的调用；或在产生新的调用，并将栈帧入栈以后，进入下一轮以执行这个新的调用；i的两种匹配分别代表了新的调用，i初始化为last+1和继续执行以前的调用

函数的主体，我们的跳转用一个switch来实现：

switch (now_pkg.nxt) {
    case 0:
        if (pos_arr > m) {
            for (int i = 1; i <= m; ++i) {
                printf("%d", arr[i]);
                putchar(i == m ? '\n' : ' ');
            }
            goto NEXT_TURN;
        }

    case 1:
        for (i; i <= n - (m - pos_arr); ++i) {
            arr[pos_arr] = i;
            tmp.nxt = 1; // 这个在循环前面定义了，不会CE
            tmp.data.pos_arr = pos_arr;
            tmp.data.last = last;
            tmp.data.i = i + 1;
            st.push(tmp);

            tmp.nxt = 0;
            tmp.data.pos_arr = pos_arr + 1;
            tmp.data.last = i;
            tmp.data.i = UNDEF;
            st.push(tmp);

            goto NEXT_TURN;
        }
}

最后放在循环前面，产生第一个函数调用并入栈的部分：

pkg_t tmp;

tmp.nxt = 0;
tmp.data.pos_arr = 1;
tmp.data.last = 0;
const int UNDEF = -1;
tmp.data.i = UNDEF;
st.push(tmp);

喜闻乐见的完整的C++代码

#include <bits/stdc++.h>


using namespace std;


int n, m;
int arr[30];


// void dfs(int pos_arr, int last) {
//     if (pos_arr > m) {
//         for (int i = 1; i <= m; ++i) {
//             printf("%d", arr[i]);
//             putchar(i == m ? '\n' : ' ');
//         }
//         return;
//     }
//     for (int i = last + 1; i <= n - (m - pos_arr); ++i) {
//         arr[pos_arr] = i;
//         dfs(pos_arr + 1, i);
//     }
// }

struct data_t {
    int pos_arr, last;
    int i;
};
struct pkg_t {
    int nxt;
    data_t data;
};
stack<pkg_t> st;


int main(void) {
    scanf("%d%d", &n, &m);

    pkg_t tmp;

    tmp.nxt = 0;
    tmp.data.pos_arr = 1;
    tmp.data.last = 0;
    const int UNDEF = -1;
    tmp.data.i = UNDEF;
    st.push(tmp);
    while (!st.empty()) {
        pkg_t now_pkg = st.top();
        st.pop();
        int pos_arr = now_pkg.data.pos_arr,
            last = now_pkg.data.last,
            i = (now_pkg.data.i == UNDEF ? last + 1 : now_pkg.data.i);
        switch (now_pkg.nxt) {
            case 0:
                if (pos_arr > m) {
                    for (int i = 1; i <= m; ++i) {
                        printf("%d", arr[i]);
                        putchar(i == m ? '\n' : ' ');
                    }
                    goto NEXT_TURN;
                }

            case 1:
                for (i; i <= n - (m - pos_arr); ++i) {
                    arr[pos_arr] = i;
                    tmp.nxt = 1;
                    tmp.data.pos_arr = pos_arr;
                    tmp.data.last = last;
                    tmp.data.i = i + 1;
                    st.push(tmp);

                    tmp.nxt = 0;
                    tmp.data.pos_arr = pos_arr + 1;
                    tmp.data.last = i;
                    tmp.data.i = UNDEF;
                    st.push(tmp);

                    goto NEXT_TURN;
                }
        }
        NEXT_TURN: /* NOTHING */ ;
    }
    return 0;
}

看完了如果有收获，是否可以点赞评论呢！