题解 P1157 【组合的输出】

· · 题解

对于这题，与[全排列问题]类似(https://www.luogu.org/problemnew/show/P1706)

不过有以下几个改变：

1、输出的个数是r而不是n

2、顺序换一换算一种（也就是要从小到大）

因此，我们只要在以下几处改一改：

源代码：

#include<bits/stdc++.h>//什么东西是万能的？头文件！
using namespace std;//听说用"cstdio"可以不写。
int n,a[10],b[10];//从左到右为：全排列个数、储存数组、标记数组。
void dfs(int x)//先别看这，看主程序！
{
    if(x==n+1)//结束条件。
    {
        for(int i=1;i<=n;i++)//从1循环到n来控制输出。
            printf("%3d",a[i]);//输出当前值，常宽为三。
        cout<<endl;//华丽地换行。
        return;//退出当前函数。
    }
    for(int i=1;i<=n;i++)//从1枚举到n。
        if(!b[i])//判断当前数(i)有没有被用过。
        {
            b[i]++;//标记。
            a[x]=i;//储存。
            dfs(x+1);//转至"dfs"函数。
            b[i]--;//取消标记。
        }
}
int main()//主程序！
{
    cin>>n;//读入n。
    dfs(1);//转至"dfs"函数。
}

现在先要把结束条件改一改，因为只要输出r个而不是n个。将

if(x==n+1)//结束条件。
    {
        for(int i=1;i<=n;i++)//从1循环到n来控制输出。
            printf("%3d",a[i]);//输出当前值，常宽为三。
        cout<<endl;//华丽地换行。
        return;//退出当前函数。
    }

中的

if(x==n+1)

改为

if(x==r+1)

然后因为要从小到大，a[x]>a[x-1]，所以枚举时第一个数也要变一变。把

for(int i=1;i<=n;i++)//从1枚举到n。
    if(!b[i])//判断当前数(i)有没有被用过。
    {
        b[i]++;//标记。
        a[x]=i;//储存。
        dfs(x+1);//转至"dfs"函数。
        b[i]--;//取消标记。
    }

中的

for(int i=1;i<=n;i++)

改为

for(int i=a[x-1]+1;i<=n;i++)

即可

贴最后程序：

#include<bits/stdc++.h>//什么东西是万能的？头文件！
using namespace std;//听说用"cstdio"可以不写。
int n,r,a[21],b[21];//从左到右为：全排列个数、一次输出个数、储存数组、标记数组。
void dfs(int x)//先别看这，看主程序！
{
    if(x==r+1)//结束条件。
    {
        for(int i=1;i<=r;i++)//从1循环到n来控制输出。
            printf("%3d",a[i]);//输出当前值，常宽为3。
        cout<<endl;//华丽地换行。
        return;//退出当前函数。
    }
    for(int i=a[x-1]+1;i<=n;i++)//从1枚举到n。
        if(!b[i])//判断当前数(i)有没有被用过。
        {
            b[i]++;//标记。
            a[x]=i;//储存。
            dfs(x+1);//转至"dfs"函数。
            b[i]--;//取消标记。
        }
}
int main()//主程序！
{
    cin>>n>>r;//读入n。
    dfs(1);//转至"dfs"函数。
}

//蒟蒻的第三篇题解，求赞！

彩蛋！

我这种方法是不是有点坑？

题目说“现要求你不用递归的方法输出所有组合”……

好尴尬……

那为什么还要放在“搜索”这一栏里？

这不是坑是什么？