递归回溯

**暴力循环函数，判断是否在已经存在，不存在则进入递归

CPP

void combination(int n,vector<int>&a)
{	
if(a.size()==n)		
{			
for(int i=0;i<a.size();i++) cout<<setw(5)<<a[i];			
cout<<endl;			
return;		
}	
for(int i=1;i<=n;i++)	
{		
if(flag(a,i))		
{			
a.push_back(i);	    	
combination(n,a);			
a.pop_back();		
 } 	
}
}

flag函数用于判断容器内是否已经存在别的元素

CPP

bool flag(vector<int>&a,int i)
{	
for(int j=0;j<a.size();j++)	
{		
if(a[j]==i) return false;	
}	
return true;
}

最后是AC代码：

CPP

#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
bool flag(vector<int>&a,int i)
{
	for(int j=0;j<a.size();j++)
	{
		if(a[j]==i) return false;
	}
	return true;
}
void combination(int n,vector<int>&a)
{
	if(a.size()==n)
		{
			for(int i=0;i<a.size();i++) cout<<setw(5)<<a[i];
			cout<<endl;
			return;
		}
	for(int i=1;i<=n;i++)
	{
		if(flag(a,i))
		{
			a.push_back(i);
	    	combination(n,a);
			a.pop_back();
		 } 
	}
}
int main()
{
	int n;cin>>n;
	vector<int> a;
	combination(n,a);
 }

文章操作

相关推荐

评论

递归回溯