491. Non-decreasing Subsequences

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Hash Table、Backtracking、Bit Manipulation

一、題目

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Example 1:

  • Input: nums = [4,6,7,7]
  • Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
  • Explanation:

Example 2:

  • Input: nums = [4,4,3,2,1]
  • Output: [[4,4]]

Constraints:

  • <= nums.length <= 15
  • -100 <= nums[i] <= 100

二、分析

  • 這一很典型的是一個 backtrack 的問題，只要熟悉回溯法的框架並注意終止條件與處理重覆子序列即可。
  • 終止條件為 i == nums.size()，此時將遍歷過的 path 加入 res，但要注意題目有規定至少要 2 個元素的子序列，故需要再加入前做確認。
  • 注意題目傳回的子序列不可重覆，故需要額外做處理。

三、解題

1. Backtracking

  • Time complexity: \(O(2^n)\)
  • Space complexity: \(O(n)\)
vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    dfs(nums, 0, path, res);
    sort(res.begin(), res.end());               // 先做排序後
    for (int i = res.size()-1; i >= 1; i--) {   // 從後面往前迭代
        if (res[i] == res[i-1]) {
            res.erase(res.begin()+i);           // 刪除重覆的序列
        }
    }
    return res;
}
void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) {
    if (i == nums.size()) {         // 終止條件
        if (path.size() > 1) {      // 滿足子序列元素大於等於2個，則加入答案
            res.push_back(path);
        }
        return;
    }
    if (path.size() == 0 || nums[i] >= path.back()) {   // 注意需滿足題意為上升序列
        path.push_back(nums[i]);    // 加入子序列
        dfs(nums, i+1, path, res);
        path.pop_back();            // 回溯法需將元素 pop 掉
    }
    dfs(nums, i+1, path, res);      // 跳過不取
}

2. Backtracking(optimized)

  • Time complexity: \(O(2^n)\)
  • Space complexity: \(O(n)\)
vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    dfs(nums, 0, path, res);
    return res;
}
void dfs(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& res) {
    if (i == nums.size()) {
        if (path.size() > 1) {
            res.push_back(path);
        }
        return;
    }
    if (path.size() == 0 || nums[i] >= path.back()) {
        path.push_back(nums[i]);
        dfs(nums, i+1, path, res);
        path.pop_back();
    }
    if (path.size() == 0 || nums[i] != path.back()) {   // 處理重覆子序列
        dfs(nums, i+1, path, res);
    }
    
}

回目錄 Catalog