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?\nLet's pretend our input had the following values {1,6,2,3
 My solution uses DFS on the array after it is sorted in ascending order. Why sort in ascending order?\nLet'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.\n\n\n\n \n\n    public class Solution {\n            public List<Integer> largestDivisibleSubset(int[] nums) {\n                \n                if(nums==null||nums.length==0)\n                {\n                    return Collections.<Integer>emptyList();\n                }\n                if(nums.length==1)\n                {\n                    List<Integer> ls=new ArrayList<Integer>(1);\n                    ls.add(nums[0]);\n                    return ls;\n                }\n               Arrays.sort(nums);\n        \n             HashMap<Integer,List<Integer>> mp=new HashMap<Integer,List<Integer>>();\n             List<Integer> maxSubset=null;\n             for(int i=0;i<nums.length;i++)\n             {\n                 List<Integer> ls=null;\n                    if(!mp.containsKey(i))\n                    {\n                        ls=dfs(i,nums,mp);\n                        \n                        \n                    }else\n                    {\n                        ls=mp.get(i);\n                    }\n                    \n                    if(maxSubset==null||ls.size()>maxSubset.size())\n                    {\n                        maxSubset=ls;\n                    }\n            }\n            return maxSubset;\n        }\n        \n         private List<Integer> dfs(int idx, int[] arr,HashMap<Integer,List<Integer>> mp)\n         {\n             if(mp.containsKey(idx))\n             {\n                 return mp.get(idx);\n             }\n             List<Integer> ls=new ArrayList<Integer>();\n             \n             for(int i=idx+1;i<arr.length;i++)\n             {\n                 if((arr[i]%arr[idx])==0)\n                 {\n                    List<Integer> r=dfs(i,arr,mp);\n                    if(r.size()>ls.size())\n                    {\n                        ls=r;\n                    }\n                    \n                 }\n             }\n            \n             ls=new ArrayList<Integer>(ls);\n             ls.add(0,arr[idx]);\n             mp.put(idx,ls);\n             return ls;\n            \n         }\n        }
['Depth-First Search', 'Java']