Largest Divisible Subset

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]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class LargestDivisibleSubset {
    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        List<Integer> large = largestDivisibleSubset(nums);
        System.out.println(Arrays.asList(large));
    }

    static List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;

        if (n == 1 || n == 0)
            return Arrays.stream(nums).boxed().collect(Collectors.toList());

        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            dp.add(new ArrayList<Integer>());
        }
        Arrays.sort(nums);
        dp.get(0).add(nums[0]);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp.get(j).size() > dp.get(i).size()
                        && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                    dp.get(i).clear();
                    dp.get(i).addAll(dp.get(j));
                }
            }
            dp.get(i).add(nums[i]);
        }
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (dp.get(i).size() > dp.get(j).size()) {
                j = i;
            }
        }
        return dp.get(j);
    }
}

C++

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

vector<int> largestDivisibleSubset(vector<int>& nums) 
{
        int n=nums.size();
        if(n==1||n==0)
              return nums;
        vector<int> dp[n];
        sort(nums.begin(),nums.end());
        dp[0].push_back(nums[0]);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
             {
                if(nums[i]>nums[j] && dp[j].size()>dp[i].size() &&(nums[i]%nums[j]==0||nums[j]%nums[i]==0))
                       dp[i]=dp[j];
             }
            dp[i].push_back(nums[i]);
        }
        int j=0;
        for(int i=0;i<n;i++)
        {
            if(dp[i].size()>dp[j].size())
            {
                j=i;
            }
        }
        return dp[j];               
}
int main()
{
    vector<int> nums ={1,2,3};
    vector<int> large=largestDivisibleSubset(nums);
    for(int i=0;i<large.size();i++)
       cout<<large[i]<<" ";
    
    return 0;
}