Here's the full solution with path reconstruction:
plaintext 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(n2). 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].