商业网站建设举例,网站页面设计需求文档,知名做网站价格,wordpress 搭建教程文章目录 46. 全排列Ⅰ. 什么是回溯算法❓❓❓Ⅱ. 回溯算法的应用1、组合问题2、排列问题3、子集问题 Ⅲ. 解题思路#xff1a;回溯 剪枝 46. 全排列
46. 全排列
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 … 文章目录 46. 全排列Ⅰ. 什么是回溯算法❓❓❓Ⅱ. 回溯算法的应用1、组合问题2、排列问题3、子集问题 Ⅲ. 解题思路回溯 剪枝 46. 全排列
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、组合问题
组合问题是指从给定的⼀组数不重复中选取出所有可能的 k 个数的组合。例如给定数集 [1,2,3]要求选取 k2 个数的所有组合。其结果为
[1, 2]
[1, 3]
[2, 3]2、排列问题
排列问题是指从给定的⼀组数可重复中选取出所有可能的 k 个数的排列。例如给定数集 [1,2,3]要求选取 k2 个数的所有排列。其结果为
[1,2]
[2,1]
[1,3]
[3,1]
[2,3]
[3,2]3、子集问题
子集问题是指从给定的一组数中选取出所有可能的子集其中每个子集中的元素可以按照任意顺序排列。例如给定数集 [1,2,3]要求选取所有可能的子集。其结果为
Ⅲ. 解题思路回溯 剪枝
首先根据题目要求我们 需要两个全局变量 ret 和 pathret 就是我们最后要返回的结果集而 path 是存放当前正在走的全排列的元素为什么要将它们设置为全局变量而不是在函数中作为引用传递其实是简化了函数需要填充的内容并且在一定程度上也简化了我们的操作尤其是后面一些题目比较说 N皇后的题目等等如果用传引用的方式的话其实是不太好控制的虽说使用全局变量之后在回溯的时候需要我们手动去恢复一下 path 的状态但是这都是值得的
对于这类排列组合的问题我们最好是能画出一棵详细一点的决策树不要想的高大上其实就是把情况枚举出来的树而已这样子有利于帮助我们理解其中要注意的细节如下面的图片所示
因为排列问题需要遍历所有的组合可能包括顺序不同的组合可能比如说 [1, 2] 和 [2, 1] 都需要满足所以我们在排列问题中就不需要使用 index 来控制每次下一层也就是树枝之间的起始位置只需要 每次都从数组下标为 0 开始遍历所有可能即可 但是这里还有一个问题就是可能会出现重复调用了某个 nums[i]比如说 [1, 2, 3] 中我们如果不对每个元素进行控制的话可能会排列出 [1, 1, 1] 等情况但是排列问题中我们 只能让每个元素都出现一次所以需要使用一个 used 数组进行判断
将 used 数组初始化为 false。因为会出现重复的情况只在一条路径上所以我们无需担心路径之间的重复所以我们让 used[i] 为 false 表示是 nums[i] 还没走过当我们在递归这条路径的下一个节点之前将 used[i] 变成 true此时下一个节点层就会知道该 nums[i] 是走过的了就不会再走了然后回溯的时候将 used[i] 变成 false这样子对同一树层是没有影响的只会对下一层的路径产生影响简单地说当我们 判断到 used[i] true也就说明上一层已经将这个元素遍历过了所以我们直接 continue 即可
说白了上面的操作其实就是一个 剪枝 的操作
对于递归函数出口我们只需要判断一下 path 数组的长度是不是等于题目给的 nums 的长度是的话说明当前序列已经是完成的了则添加到 ret 结果集中然后直接返回即可
然后就是递归函数的主体其实最重要的就是三步
处理当前层节点处理递归下一层节点递归进行回溯后的处理防止影响后面的结果回溯
可以结合下面的代码一起分析这个过程
class Solution {
private:vectorvectorint ret; // 结果集vectorint path; // 存放当前正在走的全排列的元素vectorbool used; // 标记哪个元素已经走过了用于剪枝操作防止重复
public:vectorvectorint permute(vectorint nums) {used.resize(nums.size(), false);dfs(nums);return ret;}void dfs(vectorint nums){// 递归函数出口将当前path添加到结果集中if(path.size() nums.size()){ret.push_back(path);return;}for(int i 0; i nums.size(); i) // 每次都是从0开始遍历和组合问题不一样排列问题需要遍历所有可能{// 进行剪枝操作防止结果重复if(used[i] true)continue;// 处理当前层节点path.push_back(nums[i]);used[i] true;// 递归下一层节点dfs(nums);// 进行回溯后的处理防止影响后面的结果path.pop_back();used[i] false;}}
};
