# Python solution with detailed explanation

• 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]
``````

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