day 29回溯（05）

day 29
代码随想录
2023.12.27

1. 491非递减序列
这道题跟昨天那个子集挺像的，无非就是加了个非递减、至少两个元素的条件，所以给result中添加结果是要做判断，首先个数大于1，其次就是非递减，每次添加元素都是在最后，因此这里的判断是针对最后一个元素和倒数第二个元素即可，大于或者等于，满足以上两个条件的，就push。最后运行发现结果不对，看了看，有重复子集，所以这道题也需要去重，写了这么多天这个操作，今天终于能自己写出来了。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtravel(nums,0);
        return result;
    }
    void backtravel(vector<int>& nums, int index){
        if(temp.size()>1){
           result.push_back(temp);
        }
        unordered_set<int> uniqueNums;
        for(int i=index;i<nums.size();i++){
            if (uniqueNums.count(nums[i]) > 0) {
                continue;
            }
            if (!temp.empty() && temp.back() > nums[i]) {
                continue;
            }
            temp.push_back(nums[i]);
            uniqueNums.insert(nums[i]);
            backtravel(nums, i+1);
            temp.pop_back();
        }
    }
};

2. 46全排列
新题型，首先添加时要满足数组大小等于nums大小，其次是内容要求，此时穷举的味道更重了，就是一个for循环，直接遍历所有结果，但要注意，排列，所以每个元素只能用一次，因此需要给一个判定该元素是否已经使用的变量。
总体的意思是，利用for循环遍历nums，随机找一个填充temp，当temp数量够了就push到result中，如果在添加temp时，该元素是已经使用过了，那就越过了。利用这个逻辑遍历所有结果

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtravel(nums, used);
        return result;
    }
    void backtravel(vector<int>& nums, vector<bool>& used){
        if(temp.size()==nums.size()){
            result.push_back(temp);
            return;
        }
            
        for(int i=0;i<nums.size();i++){
            if(used[i]==true)
                continue;
            temp.push_back(nums[i]);
            used[i]=true;
            backtravel(nums, used);
            temp.pop_back();
            used[i]=false;
        }
    }
};

3. 47全排列Ⅱ
这道题就是需要一个剪枝操作，递归的每一层，如果遇到相同元素，就跳过。
在这么多回溯问题中的剪枝操作，都在强调是同层的，而不是深度的，判断语句中的used[i-1]==fasle，就是强调，如果相同，且另一个还没用到，就是表示同层的，如果另一个用到了，那就是往下递归呢，也就是深度，是允许重复的。所以这一点需要琢磨一下。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> temp;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtravel(nums, used);
        return result;
    }
    void backtravel(vector<int>& nums, vector<bool>& used){
        if(temp.size()==nums.size()){
            result.push_back(temp);
            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]==true)
                continue;
            temp.push_back(nums[i]);
            used[i]=true;
            backtravel(nums, used);
            temp.pop_back();
            used[i]=false;
        }
    }
};