Java DFS Solution 86 ms with explanation

• 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);
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);