Acwing92递归实现指针型枚举

从 1∼n1∼n 这 nn 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 nn。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤151≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

#include<iostream>
#include<cstdio>
#include<algorithm>
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;
}

int main(){
	cin>>n;
	dfs(1);
	return 0;
}

记录路径

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=16;
int n;
int st[N]; //记录当前位置的状态，0表示还没考虑，1表示选他，2表示不选他
int ways[1<<15][16],cnt;

void dfs(int u){
	if(u>n)
	{
		for(int i=1;i<=n;i++)
			if(st[i]==1)
				ways[cnt][i]=i;
		cnt++;
		return ;
	}
	
	st[u]=2;
	dfs(u+1);
	st[u]=0;
	
	st[u]=1;
	dfs(u+1);
	st[u]=0;
}

int main(){
	cin>>n;
	dfs(1);
	for(int i=0;i<cnt;i++){
		for(int j=1;j<=n;j++) printf("%d",ways[i][j]);
		puts("");
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int N=16;
int n;
int st[N]; //记录当前位置的状态，0表示还没考虑，1表示选他，2表示不选他
vector<vector<int>> ways;

void dfs(int u){
	if(u>n)
	{
		vector<int> way;
		for(int i=1;i<=n;i++)
			if(st[i]==1)
				way.push_back(i);
		ways.push_back(way);		
		return ;
	}
	
	st[u]=2;
	dfs(u+1);
	st[u]=0;
	
	st[u]=1;
	dfs(u+1);
	st[u]=0;
}

int main(){
	cin>>n;
	dfs(1);
	for(int i=0;i<ways.size();i++){
		for(int j=0;j<ways[i].size();j++) printf("%d",ways[i][j]);
		puts("");
	}
	return 0;
}