Python solution with detailed explanation


  • 0
    G

    Solution

    Largest Divisible Subset https://leetcode.com/problems/largest-divisible-subset/

    Brute Force Solution

    • There is a brute force version of the problem. For every element, either we add it if we can or we do not add it. To add if we can, we compare with every member of the so_far set and test that the new addition meets the required conditions. We also add when the so_far subset is empty.
    class Solution(object):
        def helper(self, i, nums, so_far):
            if len(so_far) > len(self.max_result):
                self.max_result = [x for x in so_far]
            if i == len(nums):
                return
            else:
                self.helper(i+1, nums, so_far)
                x = nums[i]
                for y in so_far:
                    if x % y == 0 or y % x == 0:
                        continue
                    else:
                        break
                else:
                    so_far.append(x)
                    self.helper(i+1, nums, so_far)
                    so_far.pop()
            return
        
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            self.max_result = []
            self.helper(0, nums, [])
            return self.max_result
    

    Brute Force Optimized Version

    • The second version of brute force algorithm makes use of a trick. Assume we sort the array. Now say so_far is [4,6,8,12]. Then nums[i] must be more than 12 and if nums[i]%12 == 0, then all other numbers can divide nums[i]!
    class Solution(object):
        def helper(self, i, nums, so_far):
            if len(so_far) > len(self.max_result):
                self.max_result = [x for x in so_far]
            if i == len(nums):
                return
            else:
                self.helper(i+1, nums, so_far)
                if len(so_far) == 0 or (len(so_far) > 0 and nums[i] % so_far[-1] == 0):
                    so_far.append(nums[i])
                    self.helper(i+1, nums, so_far)
                    so_far.pop()
            return
        
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            self.max_result = []
            nums.sort()
            self.helper(0, nums, [])
            return self.max_result
    

    LIS Variant

    class Solution1(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums) == 0:
                return []
            nums.sort()
            LIS = [[nums[i]] for i in range(len(nums))]
            max_list_index = 0
            for i in range(1, len(nums)):
                max_j_index, max_len = i, 1
                for j in range(i):
                    if nums[i] % LIS[j][-1] == 0:
                        if len(LIS[j]) + 1 > max_len:
                            max_len,max_j_index = len(LIS[j]) + 1, j
                if max_j_index != i:
                    LIS[i].pop()
                    for k in LIS[max_j_index]:
                        LIS[i].append(k)
                    LIS[i].append(nums[i])
                if len(LIS[i]) > len(LIS[max_list_index]):
                    max_list_index = i
            return LIS[max_list_index]
    

Log in to reply
 

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