<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF890;
}

</style>

###### tags: `Leetcode`

# 491. Non-decreasing Subsequences

###### Link : https://leetcode.com/problems/non-decreasing-subsequences/description/

## 題目
回傳遞增的所有子陣列
## 程式碼 I(位元運算)
假設數組為{1, 2, 3}
則
0 0 0 => { }
0 0 1 => { 1 }
0 1 0 => { 2 }
0 1 1 => { 1, 2}
1 0 0 => { 3 }
1 0 1 =>{1 , 3}
1 1 0 => {2 , 3}
1 1 1 => {1, 2, 3}
原文網址：https://kknews.cc/code/xvekqrr.html

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        const int n = nums.size(), length = pow(2, nums.size());
        set<vector<int>> res;
        for(int i = 0;i < length;i++){
            vector<int> temp;
            for(int j = 0;j < n;j++){
                if(i & (1 << j)){
                    //遇到數字不符合條件 清空temp 跳出迴圈
                    if(temp.size() > 0 && temp[temp.size() - 1] > nums[j]){
                        temp.clear();
                        break;
                    }
                    temp.push_back(nums[j]);
                }
            }
            if(temp.size() > 1)
                res.insert(temp);
        }
        return vector(res.begin(), res.end());
    }
};

## 程式碼 II(Better Solution/Recursion)

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        //利用set避免重複的答案
        vector<int> data;
        Solve(res, data, nums, 0);
        return vector(res.begin(), res.end());
    }
    void Solve(set<vector<int>> &res, vector<int> &data, vector<int> &nums, int index){
        if(index >= nums.size()){//陣列走訪完畢
            if(data.size() >= 2){//長度大於等於二需加入答案
                res.insert(data);
            }
            return;
        }
        //如果還在遞增的話
        if(!data.size() || data.back() <= nums[index]){
            data.push_back(nums[index]);
            //有目前數字的可能
            Solve(res, data, nums, index + 1);
            data.pop_back();
        }
        //沒有目前數字的可能
        Solve(res, data, nums, index + 1);
        return;
    }
};

## Date
### 2023/1/20