[数据结构与算法]递归实现指数型枚举和组合型枚举

题目

（上面链接）
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。（spj）
递归树图
重点在第三个部分！！！ 图也很重要！

这里 引出一个剪枝的概念

即如果你能够及时确定当前问题是无解的 就不需要达到问题边界才返回结果
剪枝==优化 yyds！！！！！

如：从n个数中随机选取m个数。

一、有多少种方案 组合计数 记录状态 数组

#include<bits/stdc++.h>  
//<iostream> 有cin cout  <cstring>  <cstdio> 
using namespace std;
const int N = 16;
int n;
int st[N]; //记录状态 0为没考虑 1 选他 2 不选他 
void dfs(int u){
	if(u > n){ //只有到最后了  它才会进入这里进行返回
		for(int i = 1; i <= n; i++){
		 	if(st[i]== 1){
		 		printf("%d ", i);  		
			}
		} 
		printf("\n");
		return;
	}
	st[u] = 2;
	dfs(u+1);//第一个节点 不选的接下来 
	st[u] = 0;//恢复  就返回父节点 
	st[u] = 1;
	dfs(u+1); //第二个分支 
	st[u] = 0; 
}
main() 
{
	cin>>n;	
	dfs(1);
	return 0;
}

二、把直接输出答案 变为把答案保存

#include<bits/stdc++.h>
using namespace std;
const int N = 16;
int s[N];
int n; 
long long ways[1<<15][16],cnt = 0;  //2的十五次方种方案；
void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n;i++){
            if(s[i]==1) ways[cnt][i] = i; //那输出换为存储 同理
        }  
        cnt++;
        return ;
    }
    s[u] = 2;
    dfs(u+1);
    s[u] = 0;
    s[u] =1;
    dfs(u+1);
    s[u] = 0;
}
int main(){
    cin>>n;
    dfs(1);
    for(int i =0; i < cnt; i++){
        for(int j = 1; j <= n;j++){
            if(ways[i][j]!=0) printf("%d ",ways[i][j]);
        }
        printf("\n");
    }
    return 0;
}

三、Vector 动态数组版本

#include<bits/stdc++.h>
using namespace std;
vector<int> chosen; 
int n;
void calc(int x){
	if(x==n+1){
		for(int i = 0; i < chosen.size();i++)
			printf("%d ",chosen[i]);
		cout<<endl;	
		return ;// 一定要记得返回！
	}
	//不选分支 
	calc(x+1); //求解子问题 
	//选 的分支 
	chosen.push_back(x); 
	calc(x+1); //求解子问题 
	chosen.pop_back();//回溯到上一个问题之前  还原现
	
}
int main(){
	cin>>n;
	calc(1);
	return 0;
} 

四、递归实现组合型枚举（指数枚举再剪枝）

其实只要在上面函数开头添加判断就可以了
本题中，如果已经选择了超过m个数，或者即使再选上剩余所有的数也不够m个，就可以提前返回了。因为无解。

if(chosen.size()>m||chosen.size()+(n-x+1)<m){
	return;
}

完整解题代码
题目链接

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> chosen;//把他放到里面去动态存储
void cal(int x){
    if(chosen.size()>m||chosen.size() + (n-x + 1) < m) return ;
    if(chosen.size()==m){
        for(int i = 0; i < chosen.size();i++) printf("%d ",chosen[i]);
        cout<<endl;
        return ;
    }
    chosen.push_back(x);
    cal(x+1);
    chosen.pop_back();
    cal(x+1);
}
int main(){
    cin>>n>>m;
    cal(1);
    return 0;
}