46. 全排列015(回溯法求解)
2021/11/3 23:12:57
本文主要是介绍46. 全排列015(回溯法求解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一:题目
示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2: 输入:nums = [0,1] 输出:[[0,1],[1,0]] 示例 3: 输入:nums = [1] 输出:[[1]]
二:思路
1.思路:
1.这道题用的算法思想是回溯法,也就是穷举所有的可能,所以说回溯法也是没有办法的方法
2.那么在这里我们选用的解的空间是 排列树 也就是从根节点每次往下的分支减少一个
3.这里的在 backstrack 中 for循环相当于横向遍历,遍历到所有的元素,纵向的就是backstrack
递归 寻找一种可行解,但在递归的时候需要记录已经访问过的元素,因为每次都是从开始来遍历所有的元素
4.这里的递归终止条件是 path中的元素个数已经等于 nums.size()了,。这时也就还是排列树的
的叶节点了,记录下一个结果
2:图解过程(其选择的解的空间是排列树)
这里在选择解的空间的时候判断其用的是排列树:因为每次往下分支均减少一,而且排列树的叶节点个数为 : (n-1)! 个,n为集合元素个数
三:上码
class Solution { public: vector<vector<int>> result; vector<int>path; void backstrack(vector<int>& nums,vector<bool>& used){ //递归终止条件 当path中已经存了一种可能 if(path.size() == nums.size()){ result.push_back(path); return ; } for(int i = 0; i < nums.size(); i++){ if(used[i] == true) continue; path.push_back(nums[i]); used[i] = true;// 记录已经访问过的元素 backstrack(nums,used); //每次结束一次for循环 那么就需要将puth进去的元素剔除掉,因为最外层的for循环 path.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { /** 思路: 1.这道题用的算法思想是回溯法,也就是穷举所有的可能,所以说回溯法也是没有办法的方法 2.那么在这里我们选用的解的空间是 排列树 也就是从根节点每次往下的分支减少一个 3.这里的在 backstrack 中 for循环相当于横向遍历,遍历到所有的元素,纵向的就是backstrack 递归 寻找一种可行解,但在递归的时候需要记录已经访问过的元素,因为每次都是从开始来遍历所有的元素 4.这里的递归终止条件是 path中的元素个数已经等于 nums.size()了,。这时也就还是排列树的 的叶节点了,记录下一个结果 */ vector<bool>used(nums.size(),false); backstrack(nums,used); return result; } };
加油 boy!!!
这篇关于46. 全排列015(回溯法求解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南