回溯法输出自然数1~n的全排列。

灰太狼 2023-01-02 06:29 272阅读 0赞

**题目描述**：回溯法输出自然数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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]

//回溯框架
    void dfs(int x){    //现在处理的是第x个数 
    	if(到目的地){    //找到终点 
    		输出解；
    		return;
    	}
    	for(int i=1;i<=方案数;i++){    //一共有n中执行方案 
    		if(方案可行){    //判断当前方案的可行性 
    			保存路径；
    			dfs(x+1);
    			恢复保存前的状态  //回溯 
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]: /images/20221120/3d76efb9f3954b94a147b0dab90bbb40.png

发表评论取消回复

表情：

评论列表（有 0 条评论，272人围观）

还没有评论，来说两句吧...

相关阅读

相关回溯——46. 全排列

1 题目描述给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。 2 题目示例示例 1：输入：nums =

Bertha 。/ 2023年10月08日 16:14/ 0 赞/ 34 阅读

相关 N 皇后问题 | 回溯：N排列

> n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 > > 上图为 8 皇后问题的一种解法。 > > 给定一个整数 n，返

﹏ヽ暗。殇╰゛Y/ 2023年03月12日 10:58/ 0 赞/ 86 阅读

相关全排列回溯

public List<List<Integer>> permute(int[] nums) { int len = nums.length;

素颜马尾好姑娘i/ 2023年03月04日 10:29/ 0 赞/ 24 阅读

相关回溯法输出自然数1~n的全排列。

题目描述：回溯法输出自然数1~n的全排列。输入：n 输出：1~n的全排列。 include <bits/stdc++.h> using namesp

灰太狼/ 2023年01月02日 06:29/ 0 赞/ 273 阅读

相关【LeetCode】﹝回溯法ி﹞ 全排列、子集、组合问题

文章目录一、全排列 1.1 无重复元素全排列 1.1.1 从左向右交换

╰+哭是因爲堅強的太久メ/ 2022年12月27日 04:58/ 0 赞/ 251 阅读

相关回溯法解决全排列问题总结

1、了解全排列和回溯所谓全排列就是从n个元素中取出n个元素按照一定的顺序进行排列，所有的排列情况叫做全排列。这n个元素又分为两种情况，一种是n个元素存在重复元素，一

心已赠人/ 2022年10月09日 12:29/ 0 赞/ 243 阅读

相关 418-回溯算法-基于穷举法的全排列实现

基于穷举法的全排列实现另一种实现全排列的代码满足leetcode刷题测试用例力扣的题目：输出123的全部排列力扣要求的输出结果如下： ![在这里插入图片

末蓝、/ 2022年09月05日 01:53/ 0 赞/ 263 阅读

相关回溯算法之全排列

回溯算法是解决的这样一类问题： > 从某个数据池中每次取出一个元素，如果满足条件则将其加入到结果集中，如果不满足条件则回到数据池再次取一个元素，判断是否满足条件，直到遍历所

悠悠/ 2022年09月05日 01:41/ 0 赞/ 231 阅读

相关全排列，回溯

package com.cjy.learn; import java.util.ArrayList; import java.util.Lis

我不是女神ヾ/ 2022年08月07日 01:52/ 0 赞/ 229 阅读

相关回溯法-求全排列

回溯法入门，求一个集合的全排列，比如\{2,3,5\}的全排列为：\[\[2, 3, 5\], \[2, 5, 3\], \[3, 2, 5\], \[3, 5, 2\], \

蔚落/ 2022年08月06日 18:58/ 0 赞/ 212 阅读