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.

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	1 &lt;= nums[i] &lt;= 2 * 109
	All the integers in nums are unique.


class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1 for i in range(n)]
        hashh = [i for i in range(n)]
        ans_ind = 0
        
        for i in range(1, n):
            for j in range(0,i):
                if nums[i]%nums[j] == 0 and dp[j]+1 > dp[i]:            
                    dp[i] = dp[j]+1
                    hashh[i] = j
                    
                    # print(dp)
                    # print(hashh)
        out = []
        maxi = dp[0]
        
        for i in range(len(nums)):
            if dp[i] > maxi:
                ans_ind = i
                maxi = dp[i]
        
        while(hashh[ans_ind]!=ans_ind):
            out.append(nums[ans_ind])
            ans_ind = hashh[ans_ind]
        out.append(nums[ans_ind])
        return(out)
        
        
        
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        List<Integer> ans =new ArrayList<Integer>();
        int []dp =new int[N];
        Arrays.fill(dp,1);
        int []hash =new int[N];
        for(int i=0;i<N;i++){
            hash[i]=i;
        }
        int lastindex=0;
        int maxi =1;
        for(int i=0;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;
                    hash[i] = j;
                }
                if(dp[i] > maxi){
                    maxi = dp[i];
                    lastindex = i;
                }
            }
        }//for ends
        ans.add(nums[lastindex]);
        while(hash[lastindex] != lastindex){
            lastindex = hash[lastindex];
            ans.add(nums[lastindex]);
        }
        return ans;
    }

}
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        vector<int> ans;        
        for(int i = 0; i < n; i++)
        {                
            vector<int> tmp;
            tmp.push_back(nums[i]);
            
            // Checking the prev one
            int j = i - 1;
            while(j >= 0)
            {
                if(tmp.back() % nums[j] == 0)
                    tmp.push_back(nums[j]);
                    
                j--;
            }
            
            // Reversing the order to make it in increasing order
            reverse(tmp.begin(), tmp.end());
            
            // Checking the forward one
            j = i + 1;
            while(j < n)
            {
                if(nums[j] % tmp.back() == 0)
                    tmp.push_back(nums[j]);
                
                j++;
            }
            
            // updating the ans
            if(ans.size() < tmp.size())
                ans = tmp;
        }
        
        return ans;        
    }
};
/** https://leetcode.com/problems/largest-divisible-subset/
 * @param {number[]} nums
 * @return {number[]}
 */
var largestDivisibleSubset = function(nums) {
  // Memo
  this.memo = new Map();
  
  // Sort the array so we can do dynamic programming from last number
  // We want to start from last number because it will be the largest number, the largest number will yield the largest subset because it can be divided many times
  nums.sort((a, b) => a - b);
  
  let out = [];
  
  // Perform dynamic programming on every numbers start from the last number
  for (let i = nums.length - 1; i >= 0; i--) {
    let curr = dp(nums, i);
    
    // Update the subset output if the current subset is larger
    if (curr.length > out.length) {
      out = curr;
    }
  }
  
  return out;
};

var dp = function(nums, currIdx) {
  // Return from memo
  if (this.memo.has(currIdx) === true) {
    return this.memo.get(currIdx);
  }
  
  let currSubset = [];
  
  // Look up all numbers before `currIdx`
  for (let i = currIdx - 1; i >= 0; i--) {
    // Check if the number at `currIdx` can be divided by number at `i`
    if (nums[currIdx] % nums[i] === 0) {
      // If they can be divided, perform dynamic programming on `i` to get the subset at `i`
      let prevSubset = dp(nums, i);
      
      // If the subset at `i` is longer than current subset, update current subset
      if (prevSubset.length > currSubset.length) {
        currSubset = prevSubset;
      }
    }
  }
  
  // Create the output which include number at `currIdx`
  let out = [...currSubset, nums[currIdx]];
  
  // Set memo
  this.memo.set(currIdx, out);
  
  return out;
};
Largest Divisible Subset