491. Increasing Subsequences

這題我們先用比較偷吃步的作法, 我們用set去規避掉重複的問題

另外, 因為這必須是遞增的, 你還得去檢查是否大於當前vector的最後一個元素, 要檢查當前最大的元素, 你就會順便要考慮到他是不是空的

unordered_map不能放vector, 所以我們用set

接著用DFS去掃過全部就行了, 大於2的全部都塞到答案裡

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

如果不想用set, 你就必須把你走過的數字給記下來, 好確保她在接下來查找的過程不會重複到

class Solution {
public:
  void dfs(vector<int> &nums, int start, vector<int> &out,
           vector<vector<int>> &res) {
    if (out.size() >= 2)
      res.push_back(out);
    unordered_set<int> st;
    for (int i = start; i < nums.size(); i++) {
      if ((!out.empty() && out.back() > nums[i]) || st.count(nums[i])) {
        continue;
      }
      out.push_back(nums[i]);
      st.insert(nums[i]);
      dfs(nums, i + 1, out, res);
      out.pop_back();
    }
  }
  vector<vector<int>> findSubsequences(vector<int> &nums) {
    vector<vector<int>> res;
    vector<int> out;
    dfs(nums, 0, out, res);
    return vector<vector<int>>(res.begin(), res.end());
  }
};