做网站 就上凡科网,微信公众号怎样开通,网站建设学生作业成品,重庆装饰公司口碑十强 食用指南#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识#xff1a;回溯法经典问题之组合 ♈️今日夜电波#xff1a;爱人错过—告五人 1:11 ━━━━━━️#x1f49f;──────── 4:52 … 食用指南本文为作者刷题中认为有必要记录的题目 前置知识回溯法经典问题之组合 ♈️今日夜电波爱人错过—告五人 1:11 ━━━━━━️──────── 4:52 ◀️ ⏸ ▶️ ☰ 关注点赞收藏您的每一次鼓励都是对我莫大的支持 目录
回溯法的理解 一、全排列 二、全排列II 回溯法的理解 本文参考了一位大佬的题解详细的介绍了回溯法链接
上一篇刷题文 回溯法经典问题之子集 记住一句话for循环横向遍历递归纵向遍历回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。 一、全排列
题目链接46. 全排列
题目描述 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 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 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同 本题思路 首先采用经典的“回溯三部曲” 1、定义两个全局变量一个用来存放符合条件单一结果path一个用来存放符合条件结果的集合result。 2、回溯的主体回溯终止条件。path保存一组数据每次遍历到叶子节点再插入到result中并且回溯到上一个节点。 3、单层搜索的过程。for循环用来横向遍历递归的过程是纵向遍历。 根据题意我们做出一定的改动 我们额外定义一个bool类型的used用于确定每一个节点是否使用过以此来解决重复插入的问题并且也可以通过used对应的位置是否为false来确定是否进行后续操作。一句话概括就是只有当used[i]0时才去进行后续操作。 一图让你了解~以{1,2,3}为例 class Solution {
private:
vectorint path;
vectorvectorint result;void trackback(vectorint nums,vectorbool used)
{if(path.size()nums.size()){result.push_back(path);}for(int i0;inums.size();i){if(used[i]!1){path.push_back(nums[i]);used[i]1;trackback(nums,used);used[i]0;path.pop_back();}}
}
public:vectorvectorint permute(vectorint nums) {path.clear();result.clear();vectorbool used;used.resize(nums.size());sort(nums.begin(),nums.end());trackback(nums,used);return result;}
}; 二、全排列II
题目链接47. 全排列 II
题目描述 给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示
1 nums.length 8-10 nums[i] 10
本题思路 本题实际上为上一题的拓展题目基本上的思路跟上一题是的没什么区别的但是由于此题中的元素是可以重复的那我们就不能按照上一题只需要全部遍历一遍节点即可在这里我们需要加入剪枝操作以此来解决重复选取问题。一句话概括就是同一树枝上可以选取但是同一树层上不可以选取 即添加这段判断语句{i0nums[i-1]nums[i]used[i-1]0}来筛选重复的元素 一图让你了解~以{1,1,2}为例 class Solution {
private:
vectorint path;
vectorvectorint result;void trackback(vectorint nums,vectorbool used)
{if(path.size()nums.size()){result.push_back(path);return;}for(int i0;inums.size();i){if(i0nums[i-1]nums[i]used[i-1]0)continue;if (used[i] ! 1){path.push_back(nums[i]);used[i] 1;trackback(nums, used);used[i] 0;path.pop_back();}}
}
public:vectorvectorint permuteUnique(vectorint nums) {path.clear();result.clear();vectorbool used;used.resize(nums.size());sort(nums.begin(),nums.end());trackback(nums,used);return result;}
}; 感谢你耐心的看到这里ღ( ´ᴗ )比心如有哪里有错误请踢一脚作者o(╥﹏╥)o 给个三连再走嘛~
