# Very short Java DFS solution using Memoization

• The idea is straight-forward, just DFS look for the multiply of current number.
e.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.
The tricky part is initially (i==0) I set div to be 1 so that every number can start.
Cause every number is searched n times, so the time complexity is O(n^2)

``````public class Solution {

Map<Integer,List<Integer>> mem = new HashMap<>();

private List<Integer> helper(int[] nums, int i) {
if(mem.containsKey(i))
return mem.get(i);
List<Integer> maxLenLst = new ArrayList<>();
int div = i==0 ? 1 : nums[i-1];
for(int k=i; k<nums.length; k++) {
if(nums[k] % div == 0) {
// make a copy is crucial here, so that we won't modify the returned List reference
List<Integer> lst = new ArrayList<>(helper(nums, k+1));
if(lst.size() > maxLenLst.size())
maxLenLst = lst;
}
}
mem.put(i, maxLenLst);
return maxLenLst;
}

public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
return helper(nums, 0);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.