题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

样例

输入样例:5 3

输出样例：
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

算法1

(暴力搜索dfs)

将m看成有m个位置,每个位置考虑选取哪个数
u代表是第几个位置
start表示后续位置所选数的最小值,必须大于
一开始没有想到传一个start参数,一直在想怎么确定后续数字的范围
如果不存在这个start,每个位置总是从1开始选数,分支间会进行跳跃,导致方案重复
把输入的参数设成全局变量,那么在传参的时候就不需要进行传参考虑了

第二种的注释掉的方法是利用跟94题一样的思路,state数组用于存储每个位置的数字,
第一种方法是跟92题一样的思路,state数组用域存储每个数字是否被选中,选中为1,未选中为0

要记得进行恢复状态,恢复到上一层

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
int state[25]={0};
int used[25]={0};
int n,m;
void dfs(int u,int start)
{
    if(u>m)                        //考虑第n+1个位置应放的数字,明显超过边界,打印结果
    {
        for(int j=1;j<=n;j++)  
        {
         if(state[j]!=0)
            printf("%d ",j);
        }
        printf("\n");
        return;
    }
    for(int i=start;i<=n;i++)
    {
        if(state[i]==0)     //数值为i的元素未被选钟
        {
            state[i]=1;     //在第u个位置选取数值为i的元素
            dfs(u+1,i);     //进入下一层
            state[i]=0;     //恢复上一层状态
        }            
    }
    /*if(u>m)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%d ",state[j]);
        }
        printf("\n");
        return;
    }
    for(int i=start;i<=n;i++)
    {
        if(used[i]==0)
        {
            used[i]=1;
            state[u]=i;
            dfs(u+1,i);
            used[i]=0;
        }
    }*/
}

int main()
{
    cin>>n>>m;
    dfs(1,1);
}

另一种这里的是用state的每个二进制位,来表示第i个元素是否被选中
如果被选则为1
而这里不需要恢复现场,因为每次传入的值是对state进行改变直接传入,而没有改变state本身的值,当回到该层state就还是原来的值

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
int state;
int n,m;
void dfs(int u,int start,int state)
{
    if(start+n-u<m)
        return;  //不剪枝会爆掉

    if(start==m)
    {
        for(int i=0;i<n;i++)
        {
            if(state>>i&1)
                printf("%d ",i+1);
        }
        printf("\n");
        return;
    }
    dfs(u+1,start+1,state|1<<u);
    dfs(u+1,start,state);
}

int main()
{
    cin>>n>>m;
    dfs(0,0,0);
}