491.递增子序列

标题链接：491.递增子序列

难度指数：

有些题说明这道题是深搜。其实所有的回溯算法，你都能够说它是深搜；所有的深搜，你都能够说它是递归；

本题，咱们做一个更细致的分类，认为它还是属于回溯算法。（当然，你说是深搜也没毛病）

和子集问题有点像，但又处处是圈套

本题和刚做过的 90.子集Ⅱ 十分像，但又很不相同，很简单掉坑里。

本题是求自增子序列，❌不能够对原数组进行排序。

⚠️不能运用之前的去重逻辑！！

依旧是每个节点都是咱们要收集的成果。

树形结构：

代码思路：

去重做的是树层上的去重；

树枝上去取不同的元素，这些元素有或许数值相同。（即树枝上能够取相同数值，没毛病 ）

vector<vector<int>> result; //寄存子集的成果集
vector<int> path; //寄存子集
void backtracking(vector<int> nums, int startIndex) {
  //(能够不必停止条件)
  //要求递增子序列的大小至少为2
  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();
   } 
}

AC代码： （中心代码形式）

class Solution {
private:
  vector<vector<int>> result; //寄存子集的成果集
  vector<int> path; //寄存子集
  void backtracking(vector<int>& nums, int startIndex) {
    //(不必写停止条件)
    //要求递增序列的大小至少为2
    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;
   }
};

哈希优化：

46.全摆放

标题链接：46.全摆放

难度指数：

本题要点感受一下，摆放问题 与 组合问题，组合总和，子集问题的区别。为什么摆放问题不必 startIndex

处理摆放问题就不必运用 startIndex 了。

代码思路：

由于摆放问题，每次都要从头开始查找，例如元素1在[1,2]中现已运用过了，但是在[2,1]中还要再运用一次1。

而used数组，其实便是记载此刻path里都有哪些元素运用了，一个摆放里一个元素只能运用一次。

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;
     }
    used[i] = true;
    path.push_back(nums[i]);
    backtracking(nums, used); //回溯
    path.pop_back();
    used[i] = false;
   }
}

AC代码： （中心代码形式）

class Solution {
  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) { //path里现已录入的元素，直接跳过
        continue;
       }
      used[i] = true;
      path.push_back(nums[i]);
      backtracking(nums, used); //递归
      path.pop_back(); //回溯
      used[i] = false;
     }
   }
public:
  vector<vector<int>> permute(vector<int>& nums) {
    result.clear();
    path.clear();
    vector<bool> used(nums.size(), false);
    backtracking(nums, used);
    return result;
   }
};

47.全摆放Ⅱ

标题链接：47.全摆放Ⅱ

难度指数：

本题 便是咱们讲过的 40.组合总和II 去重逻辑 和 46.全摆放 的结合，能够先自己做一下，然后要点看一下 文章中 我讲的拓展内容。 used[i – 1] == true 也行，used[i – 1] == false 也行

代码思路：

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

AC代码： （中心代码形式）

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++) {
      //数层去重
      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;
   }
};