Leedcode刷题 | Day25_回溯算法04

 一、学习使命

• 491.递增子序列代码随想录
  
• 46.全分列
  
• 47.全分列 II
  

二、具体题目

1.491非递减子序列491. 非递减子序列 - 力扣（LeetCode）

给定一个整型数组, 你的使命是找到全部该数组的递增子序列，递增子序列的长度至少是2。
示例:

• 输入: [4, 6, 7, 7]
  
• 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
  

说明:

• 给定数组的长度不会超过15。
  
• 数组中的整数范围是 [-100,100]。
  
• 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种环境。
  

   

• 不可以排序！！！！！！！因为要求的是子序列，不是子集。
  
• 还是树层剪枝的思想，只不外因为不能排序所以不能使用之前的used数组去判定相邻元素是否相同，改为使用unordered_set大概used[201]巨细的数组记载是否重复（因为一共有200个数字）。
  
• 所以正如在哈希表：总结篇！（每逢总结必经典） (opens new window)中说的那样，数组，set，map都可以做哈希表，而且数组干的活，map和set都醒目，但假如数值范围小的话能用数组尽量用数组。
  

  unordered_set映射版本：

1. class Solution {
2. private:
3.     vector<vector<int>> result;
4.     vector<int> path;
5.     void backtracking(vector<int>& nums, int startIndex) {
6.         if (path.size() > 1) {
7.             result.push_back(path);
8.             // 注意这里不要加return，要取树上的节点
9.         }
10.         unordered_set<int> uset; // 使用set对本层元素进行去重（每次递归/每层有一个新的set）
11.         for (int i = startIndex; i < nums.size(); i++) {
12.             if ((!path.empty() && nums[i] < path.back())
13.                     || uset.find(nums[i]) != uset.end()) {
14.                     continue;
15.             }
16.             uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
17.             path.push_back(nums[i]);
18.             backtracking(nums, i + 1);
19.             path.pop_back();
20.         }
21.     }
22. public:
23.     vector<vector<int>> findSubsequences(vector<int>& nums) {
24.         result.clear();
25.         path.clear();
26.         backtracking(nums, 0);
27.         return result;
28.     }
29. };

复制代码

数组映射版本：（更快）

1. class Solution {
2. private:
3.     vector<vector<int>> result;
4.     vector<int> path;
5.     void backtracking(vector<int>& nums, int startIndex) {
6.         if (path.size() > 1) {
7.             result.push_back(path);
8.         }
9.         int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
10.         // 每次递归/每层一个数组，互不干扰，只记录本层重复情况
11.         for (int i = startIndex; i < nums.size(); i++) {
12.             if ((!path.empty() && nums[i] < path.back())
13.                     || used[nums[i] + 100] == 1) {
14.                     continue;
15.             }
16.             used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
17.             path.push_back(nums[i]);
18.             backtracking(nums, i + 1);
19.             path.pop_back();
20.         }
21.     }
22. public:
23.     vector<vector<int>> findSubsequences(vector<int>& nums) {
24.         result.clear();
25.         path.clear();
26.         backtracking(nums, 0);
27.         return result;
28.     }
29. };

复制代码

2.46全分列46. 全分列 - 力扣（LeetCode）

给定一个 没有重复 数字的序列，返回其全部可能的全分列。
示例:

• 输入: [1,2,3]
  
• 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
  

   与组合问题的区别：
  

• 每层都是从0开始搜索而不是startIndex
  
• 需要used数组记载path里都放了哪些元素了
  

    本题：nums中无重复元素
  树枝去重，true就continue；数层去重，false就continue！！！！！！

1. class Solution {
2. public:
3.     vector<vector<int>> result;
4.     vector<int> path;
5.     void backtracking (vector<int>& nums, vector<bool>& used) {
6.         // 此时说明找到了一组
7.         if (path.size() == nums.size()) {
8.             result.push_back(path);
9.             return;
10.         }
11.         for (int i = 0; i < nums.size(); i++) {
12.             if (used[i] == true) continue; // path里已经收录的元素，直接跳过
13.             used[i] = true;
14.             path.push_back(nums[i]);
15.             backtracking(nums, used);
16.             path.pop_back();
17.             used[i] = false;
18.         }
19.     }
20.     vector<vector<int>> permute(vector<int>& nums) {
21.         result.clear();
22.         path.clear();
23.         vector<bool> used(nums.size(), false);
24.         backtracking(nums, used);
25.         return result;
26.     }
27. };

复制代码

3.47全分列 II47. 全分列 II - 力扣（LeetCode）

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

   本题和上题区别：有重复元素！！！
  使用树层去重。 
    重点：

  

• 树层去重，因为进行了回溯操纵，所以之前同一层另一个分枝使用过的标记true已经被变为false，所以false才continue；
  
• 树枝去重， 因为没有进行回溯操纵，所以上一层使用过的标记true还是true，所以true才continue。
  

1. class Solution {
2. private:
3.     vector<vector<int>> result;
4.     vector<int> path;
5.     void backtracking (vector<int>& nums, vector<bool>& used) {
6.         // 此时说明找到了一组
7.         if (path.size() == nums.size()) {
8.             result.push_back(path);
9.             return;
10.         }
11.         for (int i = 0; i < nums.size(); i++) {
12.             // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
13.             // used[i - 1] == false，说明同一树层nums[i - 1]使用过
14.             // 如果同一树层nums[i - 1]使用过则直接跳过
15.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
16.                 continue;
17.             }
18.             if (used[i] == false) {
19.                 used[i] = true;
20.                 path.push_back(nums[i]);
21.                 backtracking(nums, used);
22.                 path.pop_back();
23.                 used[i] = false;
24.             }
25.         }
26.     }
27. public:
28.     vector<vector<int>> permuteUnique(vector<int>& nums) {
29.         result.clear();
30.         path.clear();
31.         sort(nums.begin(), nums.end()); // 排序
32.         vector<bool> used(nums.size(), false);
33.         backtracking(nums, used);
34.         return result;
35.     }
36. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。