Tập con chia hết lớn nhất (Largest Divisible Subset) trong C++

Mô tả bài toán

Cho tập số nguyên dương phân biệt. Tìm tập con lớn nhất sao cho mọi cặp (Si, Sj) thỏa Si % Sj == 0 hoặc Sj % Si == 0.

Ví dụ: [1,2,3] → [1,2] hoặc [1,3].

Giải thuật Quy hoạch động sau khi sắp xếp

1. Sắp xếp mảng tăng dần.
2. dp[i] = độ dài tập con lớn nhất kết thúc tại i. parent[i] = chỉ số phần tử trước trong tập con.
3. Với mỗi i, duyệt j < i: nếu nums[i] % nums[j] == 0 và dp[j] + 1 > dp[i] → cập nhật.
4. Tìm i có dp[i] lớn nhất, truy ngược qua parent để lấy tập con.

Cài đặt C++

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

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

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

int main() {
    vector<int> v = {1,2,3};
    Solution ob;
    print_vec(ob.largestDivisibleSubset(v)); // [1, 2] hoặc [1, 3]
    return 0;
}

Độ phức tạp

• Thời gian: O(n^2).
• Không gian: O(n).