Backtracking solution (TLE)
tc : O(2^n)
class Solution { List<Integer> result =null; public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); get(0,nums,new ArrayList<>()); return result; } public void get(int index, int [] nums, List<Integer> l){ if(index == nums.length){ if(result ==null || result.size() < l.size()){ result = new ArrayList<>(l); } return; } if(l.size() ==0 || nums[index] % l.get(l.size()-1)==0){ l.add(nums[index]); get(index+1,nums,l); l.remove(l.size()-1); } get(index+1,nums,l); } } 2d dp memoization (with index and prev index)
TC: O(n^2), sc: O(n^3) as n^2 for dp array and each cell will store at max n elements + space for recursive stack space which will also be O(n^2)
note: it is always better to use array that map for dp as in map we would have done some hacky stuff to get the key like i+”,”+prev or new Pair(i,prev) but using map will give tle, array dp works fine and succeeds
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); List ap[][] = new List[nums.length][nums.length+1]; for(List a[] : ap) Collections.nCopies(ap.length,null); return getWithPrevious(0,-1,nums,ap); } public List<Integer> getWithPrevious(int i, int prev, int nums[],List dp[][]){ if(i == nums.length) return new ArrayList<>(); if(dp[i][prev+1]!=null) return dp[i][prev+1]; //take List<Integer> take = new ArrayList<>(); if(prev == -1 || nums[i] % nums[prev] == 0){ take.add(nums[i]); take.addAll(getWithPrevious(i+1,i,nums,dp)); } List<Integer> donTake =new ArrayList<>(); donTake.addAll(getWithPrevious(i+1,prev,nums,dp)); List<Integer> res = take.size() > donTake.size() ? take : donTake; dp[i][prev+1] = res; return res ; } } 1d dp memoization (without prev index)
tc : O(n^2), sc: O(n^2) as we have avoided using 2 dimension but each cell in dp will store at max n elements + space for recursive stack space which will also be O(n^2)
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); List dp[] = new List[nums.length]; List<Integer> result =new ArrayList<>(); for(int i = 0;i< nums.length;i++){ List<Integer> l = topDown(i,nums,dp); if(l.size() > result.size()) result = l; } return result; } public List<Integer> topDown(int index ,int nums[],List[] dp){ //base case if(index == nums.length){ return new ArrayList<>(); } if(dp[index]!=null) return dp[index]; List<Integer> result = new ArrayList<>(); result.add(nums[index]);// this will be previous for(int k = index+1;k<nums.length;k++){ if(nums[k] % nums[index] ==0){ List<Integer> temp = new ArrayList<>(); temp.add(nums[index]); temp.addAll(topDown(k, nums,dp)); if(temp.size() > result.size()){ result = temp; } } } dp[index]= result; return result; } } Tabulation
tc: O(n^2), sc : O(n^2) with to recursive stack space
class Solution { public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); List<Integer> result = new ArrayList<>(); List dp[] = new List[nums.length]; ///initialization for(int i = 0;i< nums.length;i++){ dp[i] = new ArrayList<>(); dp[i].add(nums[i]);// smallest possible list that satisfies the condition will be the List having nums[i] atleast } for(int index = nums.length-1;index>=0;index--){ for(int k = index+1;k<nums.length;k++){ if(nums[k] % nums[index] ==0){ List<Integer> temp = new ArrayList<>(); temp.add(nums[index]); temp.addAll(dp[k]); if(temp.size() > dp[index].size()){ dp[index] = temp; } } } if(dp[index].size() > result.size()) result = dp[index]; } return result; } } 
Top comments (0)