题解 P1157 【组合的输出】

这题其实就是搜索+回溯（可是我仍然写了2小时）

这个题呢，我跟楼下们的思路有一些不一样：

首先，第一组排列一定是1~k（前k个元素），于是进行一个预处理；

接下来开始搜：

先从第k个元素搜，搜完前k-1个元素为1~k时最后一个元素的所有情况（边搜边记）；

搜完了（前k个元素填满了或任意一个元素>n了或前k个元素未填满，但目前元素已经到n了（下一步就没了））（第一种情况下输出）就回溯；

共搜k次，每次范围向前1个元素，初始值为x（目前在搜第几个元素）

搜完了就好了。

上代码：

#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;//定下一次初始值
    }
}

我的程序比楼下们省空间，因为我不用判重。所以，希望能过~