LeetCode 368 Largest Divisible Subset - Implementation

Here's the full solution with path reconstruction:

function largestDivisibleSubset(nums)
    sort(nums)
    n := length of nums
    dp := array of size n, all 1
    parent := array of size n, all -1
    maxLen := 1
    maxIdx := 0
    for i from 1 to n - 1
        for j from 0 to i - 1
            if nums[i] mod nums[j] = 0
                if dp[j] + 1 > dp[i]
                    dp[i] := dp[j] + 1
                    parent[i] := j
            if dp[i] > maxLen
                maxLen := dp[i]
                maxIdx := i
    // Reconstruct
    result := empty list
    idx := maxIdx
    while idx != -1
        result.prepend(nums[idx])
        idx := parent[idx]
    return result

Time: $O(n^2)$. Space: $O(n)$.

Sorting ensures that if nums[j] divides nums[i] and j < i, then adding nums[i] maintains divisibility for all elements dividing nums[j].