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: . Space: .
Sorting ensures that if nums[j] divides nums[i] and j < i, then adding nums[i] maintains divisibility for all elements dividing nums[j].