目录
LeetCode:491.递增子序列
基本思路
C++代码
LeetCode:46.全排列
基本思路
C++代码
LeetCode:47.全排列 II
基本思路
C++代码
LeetCode:491.递增子序列
力扣代码链接
文字讲解:LeetCode:491.递增子序列
视频讲解:回溯算法精讲,树层去重与树枝去重
基本思路
这个题目和90.子集II很像,但是不同在于90.子集II中我们是通过排序,再加一个标记数组来达到去重的目的,而本题中是不能对原数组进行排序的,排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑!
以示例1为例,抽象为树形结构如图所示:
- 递归函数参数
这里依然是定义两个全局变量,二维数组result存放结果集,数组path存放符合条件的结果。
参数:本题求子序列,很明显一个元素不能重复使用,所以需要startIndex,调整下一层递归的起始位置。
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex)
- 递归终止条件
题目要求递增子序列大小至少为2,而且不会无限递归,可以不加终止条件,startIndex每次都会加1,for循环结束即会终止。
if (path.size() > 1) {result.push_back(path);// 注意这里不要加return,因为要取树上的所有节点
}
- 单层搜索逻辑
如上图所示,显然同一父节点下的同层上使用过的元素就不能再使用了。
unordered_set<int> uset; // 使用set来对本层元素进行去重
for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();
}
C++代码
// 版本一
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);// 注意这里不要加return,要取树上的节点}unordered_set<int> uset; // 使用set对本层元素进行去重for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end()) {continue;}uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};
LeetCode:46.全排列
力扣代码链接
文字讲解:LeetCode:46.全排列
视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?
基本思路
以例一为例,抽象树形结构如下所示:
- 递归函数参数
首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组,标记已经选择的元素,如图橘黄色部分所示:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)
- 递归终止条件
可以看出叶子节点,就是收割结果的地方。当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。
// 此时说明找到了一组
if (path.size() == nums.size()) {result.push_back(path);return;
}
- 单层搜索的逻辑
排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次。
for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素,直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;
}
C++代码
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素,直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};
LeetCode:47.全排列 II
力扣代码链接
文字讲解:LeetCode:47.全排列 II
视频讲解:回溯算法求解全排列,如何去重?
基本思路
这个题目和上一题的区别在于给定一个可包含重复数字的序列,要返回所有不重复的全排列。显然需要进行去重,但是应该对树层进行去重还是树枝呢?抽象树形结构如下所示:
图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}
C++代码
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {// used[i - 1] == true,说明同一树枝nums[i - 1]使用过// used[i - 1] == false,说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == false) {used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};