dfs（深度优先）——太抽象了

1.

两种方法

#include<bits/stdc++.h>
using namespace std;
//void dfs(int index,int n,vector<int> current)
//{
//	if(index>n){
//		for(int i=0;i<current.size();i++){
//			cout<<current[i]<<" ";
//		}
//		cout<<endl;
//		return;
//	}
//	dfs(index+1,n,current);不选当前数
//	current.push_back(index);选择当前数
//	dfs(index+1,n,current);
//}
//int main()
//{
//	int n;
//	cin>>n;
//	vector<int> current;
//	dfs(1,n,current);
//	return 0;
//}
const int N=15;
int n;
int s[N];
void dfs(int x){if(x>n){  // 递归终止条件for(int i=1;i<=n;i++){if(s[i]==1){  // 只输出被标记为1的数cout<<i<<" ";}}cout<<endl;return;}// 不选当前数xs[x]=2;dfs(x+1);s[x]=0;  // 恢复状态// 选当前数xs[x]=1;dfs(x+1);s[x]=0;  // 恢复状态
}
int main(){cin>>n;dfs(1);
}

2.全排列问题（输出1到n的所有排列）

#include<bits/stdc++.h>
using namespace std;
int n;            // 用户输入的n值
const int N=20;   // 最大支持n=20
int s[N];         // 存储当前排列的数组
bool used[N];     // 标记数字是否已被使用的数组
void dfs(int u){if(u>n){  // 递归终止条件：已填完所有位置for(int i=1;i<=n;i++){cout<<s[i]<<" ";  // 输出当前排列}cout<<endl;return;}for(int i=1;i<=n;i++){  // 尝试所有可能的数字if(!used[i]){       // 如果数字i未被使用s[u] = i;       // 第u位放数字iused[i] = true;  // 标记为已使用dfs(u+1);       // 递归处理下一位used[i] = false; // 回溯：恢复状态s[u] = 0;        // 回溯：恢复状态（可省略）}}
}
int main(){cin>>n;dfs(1);  // 从第1位开始填数字return 0;
}

3.组合枚举（从1到n中选出m个数的所有组合）

#include<bits/stdc++.h>
using namespace std;
int n, m;        // n: 总数范围, m: 需要选择的数个数
const int N=20;  // 最大支持n=20
int st[N];       // 存储当前组合的数组
void dfs(int u, int start){if(u>m){  // 递归终止条件：已选够m个数for(int i=1;i<=m;i++){cout<<st[i]<<" ";  // 输出当前组合}cout<<endl;return;}for(int i=start;i<=n;i++){  // 从start开始选择，避免重复st[u] = i;              // 第u个位置选数字idfs(u+1, i+1);          // 递归选下一个数，从i+1开始st[u] = 0;              // 回溯（可省略）}
}
int main(){cin>>n>>m;dfs(1, 1);  // 从第1个位置开始选，起始数字为1return 0;
}