题解 P1157 【组合的输出】
引领天下
2017-09-02 17:29:13
这题其实就是搜索+回溯（可是我仍然写了 2 小时）
这个题呢，我跟楼下们的思路有一些不一样：
首先，第一组排列一定是 $1\sim k$（前 $k$ 个元素），于是进行一个预处理；
接下来开始搜：
先从第 $k$ 个元素搜，搜完前 $k-1$ 个元素为 $1\sim k-1$ 时最后一个元素的所有情况（边搜边记）；
搜完了（前 $k$ 个元素填满了或任意一个元素 $>n$ 了或前 $k$ 个元素未填满，但目前元素已经到 $n$ 了（下一步就没了））就回溯（第一种情况下输出）；
共搜 $k$ 次，每次范围向前 $1$ 个元素，初始值为 $x$（目前在搜第几个元素）
搜完了就好了。
上代码：
```cpp
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
int n,k,x,a[25],d;//n和k为组合中的n、r，x为目前搜到第几位，d为目前数字
void print(){//输出函数
for (int i=1;i<=k;i++)
printf ("%3d",a[i]);
printf ("\n");//用%3d输出后换行
}
void dfs(){//搜索
if (x>k){print();return;}//x>k表示当前这一种情况已经搜完，输出
if (x<k&&d==n){return;}//还没填满就已经到n了，肯定没戏了
//如果不判这个，可能会出现n=5,k=3时输出1 5 6的情况
for (int i=1;i+d<=n;i++){//加1，加2，加3……
//这个循环保证了首先元素呈上升趋势，另外，还保证了不会重复（每个元素至少比上一个大1）
d+=i;//先加上
a[x++]=d;//存起来
dfs();//搜索
x--;//减1，返回上一个节点
d-=i;//把值改回去
}
}
int main(void){
cin>>n>>k;//读入
for (int i=1;i<=k;i++)a[i]=i;//预处理第1组
x=k;//从最后一个开始搜
d=k-1;//初始值为k-1的话，第一次加1正好补为k，不会修改已经预处理好的值
while (x){//一直向前
dfs();//搜索
x--;//向前一个
d=x;//定下一次初始值
}
}
```
这样的写法因为不用判重，所以可以节约一定的空间开支。