Problem Statement

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Problem Link

Largest Divisible Subset - LeetCode

Code

vector<int> largestDivisibleSubset(vector<int>& nums) {    
sort(nums.begin(),nums.end());
    int n = nums.size();
    if(n==1)
        return nums;
    int max_len = 0,index = -1;
    vector <int> res,dp(n,1),pre(n,-1);

    for(int i=1;i<n;i++)
    {
      for(int j=i-1;j>=0;j--)
      {
          if(nums[i]%nums[j]==0&&dp[j]+1>dp[i])
          {
              dp[i] = dp[j] + 1;
              pre[i] = j;
          }
      }
     if(dp[i]>max_len)
      {
            max_len = dp[i];
            index = i;
      }
    }

    while(index!=-1)
    {
        res.push_back(nums[index]);
        index = pre[index];
    }

    return res;
}