非遞減子序列

問題描述

給了一個數組，要求給出其所有長度>=2的非遞減子序列。

思路

壓入結果的條件是path.size()>=2，回溯過程結束的條件是移動到了邊上startIndex>=num.size()
在樹中，非遞減序列，要求壓入的元素必須比之前壓入的大：if(path.empty()||nums[i]>=path.back())

問題

如果給出的數組包含重複元素，那麼答案的集合中就會包含重複的數組；

那我標記該位置的元素已經用過了，如何？````

    if(used[i]==false&&(path.empty()||nums[i]>=path.back()))
            {
            path.push_back(nums[i]);
            used[i]=true;
            backtrack(nums,i+1,used);
            path.pop_back();
            used[i]=false;
            }

這樣也是不行的，原因在於數組不同下標處的元素可能相等，這樣只是標記了一個位置的該元素，但是如果該位置後面的元素和已經遍歷過的元素有相同的，也會導致結果集中存在一樣的數組。所以重點不是對下標記錄，而是對這個元素本身的值進行記錄。使用哈希容器unorder_set<int> usedThisLeval

        for(int i=startIndex;i<nums.size();i++){
            if(usedThisLeval.contains(nums[i])){
                continue;
            }
            if(path.empty()||nums[i]>=path.back())
            {
            path.push_back(nums[i]);
            usedThisLeval.insert(nums[i]);
            backtrack(nums,i+1);
            path.pop_back();
            }
        }

但是似乎很慢！

原始思路解法代碼

class Solution {
public:
    vector<int>path;
    set<vector<int>>  res;
    void backtrack(vector<int>&nums, int startIndex){
        if(path.size()>=2){
        res.insert(path);
        }
        if(startIndex>=nums.size()){
            return;
        }
        for(int i=startIndex;i<nums.size();i++){
            if(path.empty()||nums[i]>=path.back())
            {path.push_back(nums[i]);
            backtrack(nums,i+1);
            path.pop_back();}
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        path.clear();
        res.clear();
        backtrack(nums,0);
        return vector<vector<int>>(res.begin(),res.end());
    }
};

全排列

題目描述

給定一個不含重複數字的數組，返回其所有可能的全排列。
看到題目第一眼，感覺這道題和之前做過的組合問題很相似。組合問題：在n個數中找K個數的組合。複用後發現不同，N個數的組合在組合問題中是這種情況

在回溯的這顆樹中，在移動startIndex的過程中之前的數就不會考慮進來了，但是排列問題需要考慮進來。
解決辦法是vector & used標記狀態

class Solution {
public:
    vector<int>path;
    vector<vector<int>>  res;
    void backtrack(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(used[i]==true){
                continue;//跳出本次循環
            }
            used[i]=true;
            {path.push_back(nums[i]);
            backtrack(nums,used);
            path.pop_back();
            used[i]=false;}
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        path.clear();
        res.clear();
        vector<bool>used(nums.size(),false);
        backtrack(nums,used);
        return res;   
    }
};

全排列2

問題理解

數組中出現了重複元素，使用暴力set去重，但是似乎是一種很慢的方法，相當於每次插入都要遍歷一次所有組合。

代碼

class Solution {
public:
    vector<int>path;
    vector<vector<int>>  res;
    void backtrack(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]==true){
                continue;//跳出本次循環
            }
            if(used[i]==false){
            used[i]=true;
            path.push_back(nums[i]);
            backtrack(nums,used);
            path.pop_back();
            used[i]=false;
            }

        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        path.clear();
        res.clear();
        sort(nums.begin(),nums.end());
        vector<bool>used(nums.size(),false);
        backtrack(nums,used);
        return res; 
    }
};

總結

在排列問題中使用startIndex來標記位置，因為排列是從後面每次都經過。但在組合問題中，答案集合是不關心位置的，固定元素的不同組合。首先對數組進行排序，使用used看是否用過。