My solution uses DFS on the array after it is sorted in ascending order. Why sort in ascending order?

Let's pretend our input had the following values {1,6,2,3,4,8,24,9,48} in this order . Suppose we are looking at the pair 6 and 3. We know that 6%3=0 but that doesn't mean every multiple of 3 in 3s longest subset is also a multiple of 6. For example, 9 is a multiple of 3 but not 6. However, we do know that every multiple of 6 is also a multiple of 3, hence by ordering the array such that 6 occurs after 3 we can recursively get the largest subsets of multiples of 6 (that will be comprised of values >=6) BEFORE forming longest subset of multiples of 3. . Repeat the same process for 9 (another multiple of 3) and so on and keep track of the largest subset that we can add 3 to. Cache the results so as to avoid repeated computation. For example, the subset {24,48} contains multiples of 1,2,3,4 and 6.By caching we avoid recomputing this subset for each of the aforementioned values.

```
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if(nums==null||nums.length==0)
{
return Collections.<Integer>emptyList();
}
if(nums.length==1)
{
List<Integer> ls=new ArrayList<Integer>(1);
ls.add(nums[0]);
return ls;
}
Arrays.sort(nums);
HashMap<Integer,List<Integer>> mp=new HashMap<Integer,List<Integer>>();
List<Integer> maxSubset=null;
for(int i=0;i<nums.length;i++)
{
List<Integer> ls=null;
if(!mp.containsKey(i))
{
ls=dfs(i,nums,mp);
}else
{
ls=mp.get(i);
}
if(maxSubset==null||ls.size()>maxSubset.size())
{
maxSubset=ls;
}
}
return maxSubset;
}
private List<Integer> dfs(int idx, int[] arr,HashMap<Integer,List<Integer>> mp)
{
if(mp.containsKey(idx))
{
return mp.get(idx);
}
List<Integer> ls=new ArrayList<Integer>();
for(int i=idx+1;i<arr.length;i++)
{
if((arr[i]%arr[idx])==0)
{
List<Integer> r=dfs(i,arr,mp);
if(r.size()>ls.size())
{
ls=r;
}
}
}
ls=new ArrayList<Integer>(ls);
ls.add(0,arr[idx]);
mp.put(idx,ls);
return ls;
}
}
```