Increasing Subsequences หาลำดับย่อยเพิ่มขึ้นทั้งหมดใน C++

ให้อาร์เรย์จำนวนเต็ม หา increasing subsequences ทั้งหมดที่ความยาว ≥ 2 (ไม่ซ้ำกัน)

ตัวอย่าง: [4,6,7,7] → [[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7,7],[7,7],[4,7,7]]

วิธีแก้ปัญหา (Backtracking + Dedup per Level)

1. ฟังก์ชัน solve(nums, start, temp):
   • ถ้า temp.size() > 1 → ใส่ temp ลง res
   • visited = เซตว่าง (กันซ้ำในระดับเดียวกัน)
   • วน i = start ถึง n-1:
     • ถ้า nums[i] ใน visited → ข้าม
     • ใส่ nums[i] ลง visited
     • ถ้า temp ว่างหรือ temp.back() ≤ nums[i]:
       • push nums[i] ลง temp
       • solve(nums, i+1, temp)
       • pop temp
2. จาก main เรียก solve(nums, 0, {}) คืน res

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> res;
    
    void solve(vector<int>& nums, int start, vector<int> temp) {
        if (temp.size() > 1) res.push_back(temp);
        set<int> visited;
        for (int i = start; i < nums.size(); i++) {
            int x = nums[i];
            if (visited.count(x)) continue;
            visited.insert(x);
            if (temp.empty() || temp.back() <= x) {
                temp.push_back(x);
                solve(nums, i + 1, temp);
                temp.pop_back();
            }
        }
    }
    
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        res.clear();
        vector<int> temp;
        solve(nums, 0, temp);
        return res;
    }
};

int main() {
    vector<int> v = {4,6,7,8};
    Solution ob;
    print_vector(ob.findSubsequences(v));
    return 0;
}

Input

[4,6,7,8]

Output

[[5, 6, ],[5, 6, 7, ],[5, 6, 7, 8, ],[5, 6, 8, ],[5, 7, ],[5, 7, 8, ],[5, 8, ],[6, 7, ],[6, 7, 8, ],[6, 8, ],[7, 8, ],]