Very short Java DFS solution using Memoization
The idea is straight-forward, just DFS look for the multiply of current number.\ne.g. for 2,4,7,8,16,24, first check multiply of 2, found 4 is candidate, then s
The idea is straight-forward, just DFS look for the multiply of current number.\ne.g. for 2,4,7,8,16,24, first check multiply of 2, found 4 is candidate, then search further for multiply of 4, and so on. There are duplicated calculations, so use memoization to cache the result.\nThe tricky part is initially (i==0) I set div to be 1 so that every number can start.\nCause every number is searched n times, so the time complexity is O(n^2)\n```\npublic class Solution {\n    \n    Map<Integer,List<Integer>> mem = new HashMap<>();\n    \n    private List<Integer> helper(int[] nums, int i) {\n        if(mem.containsKey(i))\n            return mem.get(i);\n        List<Integer> maxLenLst = new ArrayList<>();\n        int div = i==0 ? 1 : nums[i-1];\n        for(int k=i; k<nums.length; k++) {\n            if(nums[k] % div == 0) {\n                // make a copy is crucial here, so that we won't modify the returned List reference\n                List<Integer> lst = new ArrayList<>(helper(nums, k+1)); \n                lst.add(nums[k]);\n                if(lst.size() > maxLenLst.size())\n                    maxLenLst = lst;\n            }\n        }\n        mem.put(i, maxLenLst);\n        return maxLenLst;\n    }\n    \n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        Arrays.sort(nums);\n        return helper(nums, 0);\n    }\n}
[]