Largest Divisible Subset
Given a set of distinct positive integers nums, return the largest subset such that for every pair (a, b) in the subset, either a % b == 0 or b % a == 0.
Intuition
The divisibility constraint is transitive in a sorted array: if a | b and b | c (where | means 'divides'), then a | c. This means a valid divisible subset, when sorted, forms a chain where each element divides the next. After sorting nums, finding the longest such chain is a variant of the Longest Increasing Subsequence (LIS) problem, replacing the 'increasing' condition with 'divides'. For each element, find the best chain ending at a previous element that divides it, extend by one, and track parent pointers to reconstruct the actual subset.
The shape is: sorted array, find the longest chain where each element satisfies a transitive relation with the previous. LIS uses <, this uses %. Whenever a problem asks for the longest chain with a transitive property and you can sort to make the property directional, the LIS-like DP applies. Reconstruction with parent pointers is the standard way to recover the actual subsequence.
Approach
Sort the array so divisibility becomes a forward chain
Sorting ensures that if nums[j] divides nums[i], then j < i. This lets us build chains left to right. Without sorting, you would need to check all pairs in both directions.
DP like LIS, but with divisibility instead of inequality
Let dp[i] = length of the longest divisible chain ending at nums[i]. For each i, scan all j < i where nums[i] % nums[j] == 0. Take the best: dp[i] = max(dp[j] + 1) over all such j. Also store parent[i] = j to reconstruct the chain. Base case: dp[i] = 1 (the element alone).
Reconstruct the subset by following parent pointers
After filling the DP, find the index with the maximum dp value. Follow parent pointers backward to collect the chain. Reverse it (since we traced backward) and return. Time is O(n²) for the double loop. Space is O(n) for dp and parent.
Solution
Common pitfalls
Checking nums[j] % nums[i] == 0 instead of nums[i] % nums[j] == 0
if nums[j] % nums[i] == 0:
if nums[i] % nums[j] == 0:
After sorting, nums[j] <= nums[i] for j < i. The condition should be 'the larger divides evenly by the smaller', which is nums[i] % nums[j] == 0. Reversing it checks if the smaller divides by the larger, which is almost never true.
Forgetting to sort the array before the DP
dp = [1] * len(nums) for i in range(len(nums)):
nums.sort() dp = [1] * len(nums) for i in range(len(nums)):
Without sorting, a larger number might appear before a smaller one. The left-to-right scan would miss valid chains where the divisor appears later in the unsorted array.
Not tracking parent pointers for reconstruction
# only track dp[i], no parent max_idx = dp.index(max(dp)) return [nums[max_idx]]
parent = [-1] * n
...
result = []
while idx != -1:
result.append(nums[idx])
idx = parent[idx]The problem asks for the actual subset, not just its size. Without parent pointers, you can only return the last element of the chain, not the entire chain.
Edge cases
[1, 2, 4, 8]Every element divides every later one. The entire sorted array is a valid subset.
No element divides any other (since they are all > 1 and prime). The largest subset is any single element.
dp[0] = 1. The subset is just that element.