Largest Divisible Subset

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 109
• All the integers in nums are unique.

class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        """Implementation of finding the largest divisible subset.

        The approach uses dynamic programming to build the subset. First, the array
        is sorted. Then, for each number, it checks if any previous number divides it.
        If it does, it adds the current number to the divisible subset ending with that
        previous number.
        """
        n = len(nums)
        nums.sort()

        # dp[i] stores the largest divisible subset ending with nums[i]
        dp = [([num], 1) for num in nums]  # (subset, length)

        largest_subset = []

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j][1] + 1 > dp[i][1]:
                        dp[i] = (dp[j][0] + [nums[i]], dp[j][1] + 1)

            if not largest_subset or dp[i][1] > len(largest_subset):
                largest_subset = dp[i][0]

        return largest_subset

Explanation:

1. Initialization: The input array nums is sorted to ensure that divisibility checks can be performed sequentially. dp[i] is initialized such that each number nums[i] forms a subset of length 1, i.e., ([nums[i]], 1). This means each number initially is considered as the end of a divisible subset of length 1.
2. Dynamic Programming: The code iterates through the sorted array. For each number nums[i], it checks all preceding numbers nums[j] to find if nums[i] is divisible by nums[j]. If it is, it means nums[i] can be added to the divisible subset ending at nums[j]. The length of the subset ending at nums[i] is updated only if adding nums[i] to the subset ending at nums[j] results in a longer subset.
3. Updating dp[i]: Specifically, if nums[i] % nums[j] == 0, and if the length of the subset ending at nums[j] plus 1 is greater than the current length of the subset ending at nums[i], then dp[i] is updated to be the subset ending at nums[j] plus nums[i], and the length is incremented by 1.
4. Tracking the Largest Subset: During the iteration, the largest_subset variable keeps track of the largest divisible subset found so far. After each iteration for nums[i], it checks if the length of the subset ending at nums[i] is greater than the length of the current largest_subset. If it is, largest_subset is updated.
5. Return Value: Finally, the function returns the largest_subset found.

Example:

Consider nums = [1, 2, 4, 8]. The steps would be:

• Sort nums to get [1, 2, 4, 8].
• Initialize dp to [([1], 1), ([2], 1), ([4], 1), ([8], 1)].
• Iterate and update dp:
  • For nums[1] = 2, it's divisible by nums[0] = 1. So, dp[1] becomes ([1, 2], 2).
  • For nums[2] = 4, it's divisible by nums[0] = 1. So, dp[2] becomes ([1, 4], 2). Also, it's divisible by nums[1] = 2. So, dp[2] becomes ([1, 2, 4], 3).
  • For nums[3] = 8, it's divisible by nums[0] = 1. So, dp[3] becomes ([1, 8], 2). It's divisible by nums[1] = 2. So, dp[3] becomes ([1, 2, 8], 3). It's divisible by nums[2] = 4. So, dp[3] becomes ([1, 2, 4, 8], 4).
• The largest_subset will be [1, 2, 4, 8].

Big O Analysis:

• Time Complexity: O(n^2), where n is the number of elements in nums. This is due to the nested loops in the dynamic programming approach.
• Space Complexity: O(n), where n is the number of elements in nums. This is because the dp list stores a subset for each number in nums.