代码随想录算法训练营第二十八天 | 491.递增子序列，46.全排列，47.全排列 II

一、参考资料

递增子序列

题目链接/文章讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v

全排列

题目链接/文章讲解：https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

视频讲解：https://www.bilibili.com/video/BV19v4y1S79W

全排列 II

题目链接/文章讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm

二、LeetCode491.递增子序列

https://leetcode.cn/problems/non-decreasing-subsequences/description/

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]

切割问题可以抽象为树型结构，如图：

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {res.push_back(path);}unordered_set<int> uset;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) {backtracking(nums, 0);return res;}
};

带注释版：

// 版本一
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;}
};

优化版本【用数组做哈希表】

// 版本二
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);}int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| used[nums[i] + 100] == 1) {continue;}used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了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;}
};

三、LeetCode46.全排列

https://leetcode.cn/problems/permutations/description/

给定一个不含重复数字的数组 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] <= 10
nums 中的所有整数 互不相同

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;}
};

排列问题的不同：

• 每层都是从0开始搜索而不是startIndex

• 需要used数组记录path里都放了哪些元素了

我写的如下~【唔，理解了思路】

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking (vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {res.push_back(path);return ;}// unordered_set<int> uset;for (int i = 0; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return res;}
};

四、LeetCode47.全排列 II

https://leetcode.cn/problems/permutations-ii/description/

给定一个可包含重复数字的序列 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

在40.组合总和II (opens new window)、90.子集II (opens new window)我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

带注释版：

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;}
};

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

我写的这个题的代码：

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking (vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {res.push_back(path);return ;}for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue;}if (!used[i]) {path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}}public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return res;}
};

拓展：

去重的关键部分代码：

if(i >0&& nums[i]== nums[i -1]&& used[i -1]==false){continue;}

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

if(i >0&& nums[i]== nums[i -1]&& used[i -1]==true){continue;}

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

例子：[1,1,1]

(1) 树层上去重(used[i - 1] == false)，的树形结构如下：

(2) 树枝上去重（used[i - 1] == true）的树型结构如下：

因此，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

今日总结：

2023-02-14 终于补完了代码和博客~

回溯专题马上就结束辽，今天下午再把三个难题争取克服一下，晚上开始写贪心题目、复习数组专题，今日目标就是赶上进度！

下集预告：

● 332.重新安排行程

● 51. N皇后

● 37. 解数独

● 回溯专题总结

继续加油哈小赵~