Largest Divisible Subset is a classic dynamic programming problem that shows up in coding interviews because it looks mathematical, but the real skill is building the right structure.
You are given a set (or array) of distinct positive integers. You need to return the largest subset where every pair of numbers in the subset satisfies a divisibility rule.
The rule is simple: for any two numbers in the subset, either one divides the other.
That means if your subset contains a and b, then a % b == 0 or b % a == 0 must be true.
The goal is not to find all such subsets. The goal is to find one of the maximum size.
This problem becomes interesting because divisibility is not “local” in the same way sorting is. Two numbers can individually divide a third but not divide each other. So you need a strategy that ensures the entire subset stays consistent.
Why a direct approach is slow
A tempting approach is to try different combinations and check whether all pairs are divisible. That quickly becomes expensive because the number of subsets grows exponentially.
Even if you try to build subsets greedily, you can get stuck. Choosing a number that works now might block a longer chain later.
What you need is a method that systematically builds the best answer while reusing previous work. That is where dynamic programming fits perfectly.
Want to explore more coding problem solutions? Check out the Longest Univalue Path and 3Sum Closest coding problem solutions.
The key insight that simplifies everything
Divisibility behaves nicely when numbers are sorted.
If you sort the array in increasing order, then for any valid divisible subset, you can think of it as a chain where smaller numbers divide larger numbers.
Once sorted, you no longer need to worry about the “either divides the other” condition in both directions. You can focus on building upward: earlier numbers can potentially divide later numbers.
This converts the problem into something that feels like “Longest Increasing Subsequence,” except the condition is divisibility instead of increasing order.
How the solution works conceptually
Start by sorting the numbers from smallest to largest.
Now imagine you are deciding, for each number, what is the best divisible subset that ends with that number.
For every number at position i, look at all earlier numbers j < i.
If the current number is divisible by a previous number, then any valid subset ending at j can be extended by adding the current number.
So the “best ending here” value becomes:
best_at_i = 1 + max(best_at_j) for all j where nums[i] is divisible by nums[j].
If no earlier number divides it, then the best subset ending here is just the number itself, with length 1.
This is the core dynamic programming idea.
How you reconstruct the actual subset
Counting the length is not enough. The problem asks you to return the subset.
So while you compute the best chain length for each number, you also track a “parent pointer” or “previous index” that tells you which earlier number led to the best extension.
At the end, you find the index where the chain length is maximum.
Then you walk backward using the parent links to rebuild the subset in reverse order.
Finally, reverse it to return the subset from smallest to largest.
Why this approach is reliable
Sorting ensures you only extend from smaller to larger numbers.
The divisibility check ensures every step is valid.
The dynamic programming table ensures you never miss a longer chain, because you evaluate all possible ways to end at each number.
This is exactly the kind of solution interviewers like: simple structure, clear correctness, and solid performance.
Complexity in plain terms
The solution typically runs in quadratic time because for each number, you may check all earlier numbers.
For most interview constraints, this is fast enough and considered the standard approach.
Memory usage stays reasonable because you store a few arrays: one for lengths and one for parent links.
Top comments (0)