# 292 ms Python solution

• The idea is to put the (sorted) numbers into buckets one by one and make sure each number is divisible by one number in previous buckets. So the index of the bucket is the max size of a set.

``````Num      1, 2, 3, 4, 6, 8, 9, 12, 24, 36

bucket   1  2  3  4  5
-----------------------
1  2  4  8 24
3  6 12 36
9
``````

After doing this, all I need to do is find a path between the first bucket and the last. We can do this using DFS but I choose to put a tuple (d, p) into buckets instead of a number where f is the divider and p is the number.

``````class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums = sorted(nums)
buckets = [None, []]
if len(nums) < 2:
return nums
max_len = 0
for n in nums:
atemp = max_len + 1
placed = False
while atemp > 0 and not placed:
if atemp == 1:
buckets[1].append((None, n))
max_len = max(max_len, atemp)
placed = True
else:
for _, p in buckets[atemp-1]:
if n % p == 0:
while len(buckets) - 1 < atemp:
buckets.append([])
buckets[atemp].append((p, n))
max_len = max(max_len, atemp)
placed = True
break
atemp -= 1
ans = [buckets[-1][0][1]]
target = buckets[-1][0][0]
for i in xrange(max_len-1, 0, -1):
for d, p in buckets[i]:
if p == target:
ans.insert(0, p)
target = d
break
return ans
``````

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