ชุดย่อยที่หารลงตัวมากที่สุดใน C++

ให้ชุดจำนวนเต็มบวกที่ไม่ซ้ำกัน หาชุดย่อยขนาดใหญ่ที่สุดที่ทุกคู่ (Si, Sj) สอดคล้อง Si % Sj == 0 หรือ Sj % Si == 0

ตัวอย่าง: [1,2,3] → [1,2] หรือ [1,3]

ขั้นตอนการแก้ปัญหา (DP + Backtracking)

1. เรียงอาร์เรย์ nums จากน้อยไปมาก
2. dp[i] = ความยาวชุดย่อยที่หารลงตัวได้มากที่สุดที่ลงท้ายด้วย nums[i]
3. par[i] = index ก่อนหน้าในลำดับ (เพื่อ reconstruct)
4. วน i = 1..n-1, j = 0..i-1:
   • ถ้า nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i] → อัปเดต dp[i], par[i]
5. หา endpoint ที่ dp สูงสุด
6. ย้อนกลับด้วย par สร้างชุดย่อย, reverse แล้วคืน

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

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size();
        if (!n) return {};
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1), par(n);
        int endPoint = 0, maxLen = 1;
        for (int i = 1; i < n; i++) {
            par[i] = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    par[i] = j;
                }
            }
            if (dp[i] > maxLen) { maxLen = dp[i]; endPoint = i; }
        }
        while (true) {
            ret.push_back(nums[endPoint]);
            if (endPoint == par[endPoint]) break;
            endPoint = par[endPoint];
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3};
    print_vector(ob.largestDivisibleSubset(v));
}

Input

[1,2,3]

Output

[1, 2, ]