Very short Java DFS solution using Memoization


  • 1

    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)); 
                    lst.add(nums[k]);
                    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);
        }
    }

Log in to reply
 

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