368. 最大整除子集*

[MyLinChi]

问题

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

 

示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-divisible-subset
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

方法一：回溯法（超时）

class Solution {
private:
    vector<int> nums;
    vector<bool> flag;
    vector<bool> resflag;
    int cnt;
    int fcnt;
    bool compatible(int k) {
        for (int i = 0; i < nums.size(); ++i) {
            if (flag[i] && nums[i] % nums[k] != 0 && nums[k] % nums[i] != 0)
                return false;
        }
        return true;
    }

    void helper(int s) {
        if(s>=nums.size())return;
        if (compatible(s)) {
            flag[s] = true;
            if (++cnt > fcnt) {
                fcnt = cnt;
                resflag = flag;
            }
            helper(s+1);
            flag[s] = false;
            --cnt;
        }
        helper(s+1);
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        this->nums = nums;
        flag = vector<bool>(nums.size(), false);
        resflag = vector<bool>(nums.size(), false);
        cnt = 0;
        fcnt = 0;
        helper(0);
        vector<int> res;
        for (int i = 0; i < resflag.size(); ++i) {
            if (resflag[i])
                res.push_back(nums[i]);
        }
        return res;
    }
};

方法二：(动态规划，类似于求最长递增子序列，只是判断整数集时先排序可以简化判断)
参考：官方题解

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int len = nums.size();
        if(len==0)return {};
        vector<int> last(len);
        vector<int> cnt(len);
        sort(nums.begin(),nums.end());
        int resIndex = 0;
        vector<int> res;
        for(int i=0;i<nums.size();++i){
            if(i==0){
                last[i]=-1;
                cnt[i] = 1;
            }else{   
                int index = -1;
                int maxcnt = 0;
                for(int k=0;k<i;++k){
                    if(nums[i]%nums[k]==0 && cnt[k]>maxcnt){
                        index = k;
                        maxcnt = cnt[k];
                    }
                }
                if(index>=0){
                    last[i] = index;
                    cnt[i] = maxcnt+1;
                }else{
                    last[i] = -1;
                    cnt[i] = 1;
                }
            }
            if(cnt[resIndex]<cnt[i])resIndex = i;
        }
        for(;resIndex>=0;resIndex = last[resIndex])res.push_back(nums[resIndex]);
        return res;
    }
};