题目描述
从 1∼n这 n个整数中随机选取任意多个,输出所有可能的选择方案。然后不管顺序。
算法
递归
解题思路
这图就是视频讲解里面的
本题的主要的一个思想就是,在1-n这些数里面,递归枚举所有数字选与不选的情况。
关键在于这段代码
st[m]=1;//选
dfs(m+1);//选完后往下走
st[m]=0;//恢复现场
dfs(m+1);//对于此时这个数,上面已经dfs了选它的情况,现在就是dfs不选的情况
然后后面不用恢复现场因为这个本来就是‘0’ 在bool数组中初始默认都是false的
这个代码没有和y总一样 分为 0没确定,1选,2不选。因为在for循环输出的时候,if(st[i]==1) cout<<i<<’ ‘;都是
看你st[i]此时是否为1,不用理是不是2。这个算法是一直往后走的,第一个数判断完马上dfs(m+1),后面的数都是‘新’的,所以全面那个数是0还是2都无所谓,只要不是1就不输出。
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=17;
bool st[N];
int n;
void dfs(int m){
if(m>n){
for(int i=1;i<=n;i++)
if(st[i]==1) cout<<i<<' ';
cout<<endl;
return ;
}
st[m]=1;
dfs(m+1);
st[m]=0;
dfs(m+1);
}
int main(){
cin>>n;
dfs(1);
return 0;
}