368.Largest Divisible Subset

Tags: [dp], [math], [path], [trace], [parent], [parent_trace], [sort]

Link: https://leetcode.com/problems/largest-divisible-subset/#/description

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si% Sj= 0 or Sj% Si= 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]
Result: [1,2,4,8]

Solution: DP, Math, Parent Trace

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        nums.sort()
        size = len(nums)

        # DP formula:
        # f[i] = max(f[j] + 1), 0<= j < i and ([i] >= [j] and [i] % [j] == 0)
        f = [0 for _ in xrange(size)]
        f[0] = 1

        previous_elem_indices = [None for _ in xrange(size)]
        for i in xrange(1, size):
            for j in xrange(i):
                if nums[i] % nums[j] == 0 and (f[i] < f[j] + 1):
                    f[i] = f[j] + 1
                    previous_elem_indices[i] = j

        largest_subset_end_index = None
        max_len = 0
        for i in xrange(len(f)):
            if f[i] > max_len:
                max_len = f[i]
                largest_subset_end_index = i

        result = [nums[largest_subset_end_index]]
        previous_elem_index = previous_elem_indices[largest_subset_end_index]
        while previous_elem_index is not None:
            result.append(nums[previous_elem_index])
            previous_elem_index = previous_elem_indices[previous_elem_index]

        result.reverse()
        return result

Revelation:

• We have to sort the nums, because for example, nums = [488, 122, 366], 488 % 122 == 0, and 366 % 122 == 0, but 488 % 366 != 0 and 366 % 488 != 0.
• Knowledge: if a < b < c, if b % a == 0 and c % b == 0, we can get c % a == 0. This is the reason why we have to sort the given nums.
• Using 'previous_elem_indices' to record the index of the element before the current element, which both elements belongs to the same subset. Then once we find the index of end element of the largest subset, we can use previous_elem_indices to back trace to find the entire sequence.

Note:

• Time complexity = O(n^2), n is the number of given numbers.
• Space complexity = O(n), n is the number of given numbers.

Time Limited Exceeded

class Solution(object):

    def __init__(self):
        self.largest_set = []

    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        nums.sort()
        buff = []
        self.largest_divisible_subset_helper(nums, 0, buff)
        return self.largest_set


    def largest_divisible_subset_helper(self, nums, index, buff):
        # base case
        if index >= len(nums):
            if len(self.largest_set) < len(buff):
                self.largest_set = list(buff)

            return

        for i in xrange(index, len(nums)):
            if not buff or buff[-1] % nums[i] == 0 or nums[i] % buff[-1] == 0:
                buff.append(nums[i])
                self.largest_divisible_subset_helper(nums, i + 1, buff)
                buff.pop()

            self.largest_divisible_subset_helper(nums, i + 1, buff)

Revelation:

• Brute force to try all possible ways to build the subset, and find the largest one.

Note:

• Here we still need to sort the nums, the reason has been explained above.
• Time complexity = O(2^n), n is the number of given numbers.
• Space complexity = O(n), the depth of recursion is O(n), and the max size of the buff = O(n).