题目描述:回溯法输出自然数1~n的全排列。
输入:n
输出:1~n的全排列。
#include <bits/stdc++.h>using namespace std;int vis[100];int ans[100];int n;void dfs(int x){//现在处理的是第x个数 if(x>n){//找到终点 for(int i=1;i<=n;i++){//输出 cout<<ans[i]<<" "; }cout<<endl;return;}for(int i=1;i<=n;i++){//一共有n中执行方案 if(vis[i]==0){//判断当前方案的可行性 vis[i]=1; //标记当前已被使用 ans[x]=i; //记录当前使用的数 dfs(x+1);vis[i]=0; //回溯 }}}int main(){cin>>n;dfs(1); //从1开始尝试 return 0;}
//回溯框架void dfs(int x){//现在处理的是第x个数 if(到目的地){//找到终点 输出解;return;}for(int i=1;i<=方案数;i++){//一共有n中执行方案 if(方案可行){//判断当前方案的可行性 保存路径;dfs(x+1);恢复保存前的状态 //回溯 }}}
如果觉得《回溯法输出自然数1~n的全排列。》对你有帮助,请点赞、收藏,并留下你的观点哦!