Largest Divisible subset

Problem Backtracking solution (TLE) tc : O(2^n) class Solution { List result =null; public List largestDivisibleSubset(int[] nums) { Arrays.sort(nums); get(0,nums,new ArrayList()); return result; } public void get(int index, int [] nums, List l){ if(index == nums.length){ if(result ==null || result.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 largestDivisibleSubset(int[] nums) { Arrays.sort(nums); List dp[] = new List[nums.length]; List result =new ArrayList(); for(int i = 0;i result.size()) result = l; } return result; } public List topDown(int index ,int nums[],List[] dp){ //base case if(index == nums.length){ return new ArrayList(); } if(dp[index]!=null) return dp[index]; List result = new ArrayList(); result.add(nums[index]);// this will be previous for(int k = index+1;k 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 largestDivisibleSubset(int[] nums) { Arrays.sort(nums); List result = new ArrayList(); List dp[] = new List[nums.length]; ///initialization for(int i = 0;i=0;index--){ for(int k = index+1;k dp[index].size()){ dp[index] = temp; } } } if(dp[index].size() > result.size()) result = dp[index]; } return result; } }

Apr 6, 2025 - 11:58

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;
    }
}