递归回溯

LJ2921589677 · 2025-08-07 10:53:54 · 题解

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

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函数用于判断容器内是否已经存在别的元素

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

最后是AC代码：

#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);
 }