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.
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 2 * 10⁹
- All the integers in nums are unique.
Intuition
Largest divisible subset finds the biggest subset where every pair divides one another. Checking all pairs in a candidate subset sounds necessary, but a property of divisibility removes most of the work.
Divisibility is transitive: if a divides b and b divides c, then a divides c. So in a sorted subset, checking each element against only its immediate predecessor is enough:
- Sorting first means every element need only be tested against the largest element chosen so far, not against all of them.
Without sorting, no such ordering exists and the pairwise property cannot be reduced.
The structure is then exactly Longest Increasing Subsequence with divisibility replacing the comparison. Define dp[i] as the size of the largest valid subset ending at index i. For each i, look at every earlier j, and if nums[i] % nums[j] == 0, consider extending that subset.
Reconstructing the subset — not just its size — needs a parent array recording which j gave each best value. Following the parent chain backwards from the largest dp value rebuilds the subset, then reverse it.
That reconstruction is where solutions fail. Tracking only sizes answers a different question than the one asked, which requires the elements themselves.
The maximum is not necessarily at the last index, so the whole dp array must be scanned to find where the chain starts.
An empty input returns an empty list, and a single element is trivially valid since a number divides itself.
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
Before reading on: price up what sorting first costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n²) time and O(n) space.
Sort the array first
Sorting is what makes the pairwise condition tractable — without an ordering, every pair must be checked and no reduction is possible.
Exploit transitivity
If a divides b and b divides c, then a divides c. So each element need only be tested against the largest already chosen, not against all of them.
Define the LIS-style state
dp[i] is the size of the largest valid subset ending at index i. This is Longest Increasing Subsequence with divisibility replacing the comparison.
Extend on divisibility
For each i, scan every earlier j. When nums[i] % nums[j] == 0 and extending improves dp[i], take that extension.
Record parents for reconstruction
Store which j produced each best value. Tracking only sizes answers a different question — the problem requires the elements themselves.
Rebuild from the maximum
Scan the whole dp array for the largest value — it is not necessarily at the last index — then follow the parent chain back and reverse it.
Cost of the approach
Sorting is O(n log n) and the nested scan O(n²) time, which dominates. Space is O(n) for the dp and parent arrays.
Solution & live demo
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.