First, I sorted the input list nums to ensure that for any two elements nums[i] and nums[j], where i > j, nums[i] % nums[j] is easy to check. I then used a dp array where dp[i] stores the size of the largest divisible subset ending at index i. I also tracked the prev index to reconstruct the subset at the end. I returned the largest subset by backtracking from the maximum value in dp.
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums:
return []
nums.sort()
n = len(nums)
dp = [1] * n
prev = [-1] * n
max_len = 1
max_index = 0
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j
if dp[i] > max_len:
max_len = dp[i]
max_index = i
result = []
while max_index != -1:
result.append(nums[max_index])
max_index = prev[max_index]
return result[::-1]- Time: O(n^2)
- Space: O(n)
