递归子序列
leetcode：491. 非递减子序列
回溯法
思路
类似子集Ⅱ，每个元素大于二的节点都放入结果集。
在填充path的过程中，检查是否满足非严格递增（是否等于末元素或比它大）。
但是由于本题不能排序，之前的去重策略（数组排序，检查nums[i - 1] == nums[i] && used[i - 1] == false）要调整。
设置一个j，向前寻找begin ~ i - 1范围内，是否存在和nums[i]相等的值，如果存在则说明重复，跳过本轮循环。
复杂度分析
时间复杂度：
- 在 backtracking 函数中，采用了回溯法来找到所有可能的递增子序列，其中使用了循环来遍历数组 nums，时间复杂度为 O(2^n)，其中 n 为数组 nums 的长度。
- 在找到一个递增子序列时，会将其加入到 result 中，这里涉及到复制 path 数组到 result 中，复制的时间复杂度为 O(n)，其中 n 为 path 数组的长度。
- 因此，总体时间复杂度为 O(2^n * n)，其中 n 为数组 nums 的长度。
空间复杂度：
- 使用了 path 和 result 两个额外的数组来保存递增子序列和最终结果，空间复杂度取决于所有递增子序列的数量。最坏情况下，递增子序列的数量为 O(2^n)，因此空间复杂度也为 O(2^n)。
注意点
-
树层去重的方法：
-
数组排序+条件判断
i > 0 && nums[i - 1] == nums[i] && used[i - 1]== false -
向前寻找，
begin ~ i - 1是否有相等的元素.int j = i - 1; while(j >= begin) j--; if(j >= begin) continue; // 如果j最后>=begin，说明有相等元素，跳过循环，树层去重
-
-
如果用set的话，放入元素的方法叫
insert。
代码实现
版本一，不用used，向前寻找去重：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
void backtracking(vector<int>& nums,int begin){
if(path.size() >= 2){
result.push_back(path);
}
// 树层要去重
// 对比上一元素,非严格递增才放进去
for(int i = begin;i < nums.size();i++){
// 这里没有排序，不能简单比较nums[i - 1]==nums[i]
// 但可以向前寻找相同元素
int j = i - 1;
while(j >= begin && nums[j] != nums[i]) j--;
if(j >= begin ) continue; // 如果找到了，那么说明重复，继续
if(path.size() == 0 || (path.size() > 0 && nums[i] >= path[path.size() - 1 ]) ){
path.push_back(nums[i]);
backtracking(nums,i + 1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
版本二，每层用set去重：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
void backtracking(vector<int>& nums,int begin){
if(path.size() >= 2){
result.push_back(path);
}
// 树层要去重
// 对比上一元素,非严格递增才放进去
// set去重版，每层使用过的元素
unordered_set<int> uset;
for(int i = begin;i < nums.size();i++){
if(uset.find(nums[i]) != uset.end() ) continue;
if(path.empty() || nums[i] >= path.back() ){
uset.insert(nums[i]); // 放入元素
path.push_back(nums[i]);
backtracking(nums,i + 1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
版本三，用数组建立哈希映射：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
void backtracking(vector<int>& nums,int begin){
if(path.size() >= 2){
result.push_back(path);
}
// 树层要去重
// 对比上一元素,非严格递增才放进去
// 数组哈希法
int used[201] = {0};
for(int i = begin;i < nums.size();i++){
if(used[nums[i] + 100] == 1) continue;
if(path.empty() || nums[i] >= path.back() ){
used[nums[i] + 100] = 1; // 放入元素
path.push_back(nums[i]);
backtracking(nums,i + 1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
全排列
leetcode：46. 全排列
回溯法
思想
逻辑是遍历没用过的元素，无所谓顺序，每次都要用完所有元素。
用used数组标记使用过的元素，进行排除。
复杂度分析
时间复杂度：O(N!)
- backtracking 函数中的 for 循环会遍历 nums 数组，时间复杂度为 O(N)，其中 N 是 nums 的长度。
- 在每次递归调用中，都会将当前元素加入 path 中，然后继续向下递归，因此总体的时间复杂度可以表示为 O(N!)，因为每个元素都有 N 种选择，所以共有 N! 种可能的排列方式。
空间复杂度：O(N + N!)
- path 数组的最大长度取决于输入 nums 数组的长度，因为每个元素都有可能加入或不加入 path 中，所以 path 的空间复杂度为 O(N)。
- result 数组存储所有符合条件的排列，最坏情况下可能包含 N! 个排列，因此空间复杂度为 O(N!)。
- used 数组占用了额外的 O(N) 空间。
- 整体空间复杂度为 O(N + N!)。
注意点
- 别把赋值写成==......
代码实现
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
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.push_back(nums[i]);
used[i] = true;
backtracking(nums,used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(),false);
backtracking(nums,used);
return result;
}
};
全排列Ⅱ
leetcode：47. 全排列 II
回溯法
思想
（都打出肌肉记忆了，但其实并没有想的很清楚）
全排列的基础上去重。
去重就是排序+条件判断。
复杂度分析
时间复杂度：
- n 个元素一共有 n! 中排列方案。
- 而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组。
- 最差情况所有元素都是唯一的。复杂度和全排列Ⅰ都是 O(n! * n)
空间复杂度：O(n)
回溯树的深度取决于我们有多少个元素。
注意点
- 这题
used[i - 1] == false也行而used[i - 1] == true也行。但是一定要加上两者之一，因为 used[i - 1] 要一直是 true 或者一直是false 才可以，而不是 一会是true 一会又是false。 所以这个条件要写上。
代码实现
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
// 去重版的全排列
// 去重 = 排序 + 条件判断
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]) continue;
if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums,used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used);
return result;
}
};