Largest Divisible Subset

Medium20–25 min

Topics

Dynamic ProgrammingArraySorting

Companies

AmazonBloombergAdobe

Given an array of distinct integers, find the largest subset where every pair of numbers is compatible in a division sense — for any two numbers in the subset, the larger one is evenly divisible by the smaller one. Sorting the numbers first turns this into a subsequence problem: once ascending, any valid subset lines up in that same increasing order, because a bigger multiple can only be evenly divisible by a smaller factor that came before it. That makes it possible to ask, for every number, "what's the best divisible chain that ends here?" — check every earlier, smaller number, and whenever it evenly divides the current one, the chain ending there could be extended. Solving that sub-problem once per number, in ascending order, and remembering which earlier number produced each best chain, is enough to reconstruct the whole thing afterward.

Test Case 1:

Input:nums = [2, 4, 5]

Output:[2, 4]

Explanation:2 divides 4, giving the subset [2, 4] of size 2. 5 can't extend it (4 doesn't divide 5, and pairing 2 with 5 alone is no better), so size 2 is the best achievable.

Test Case 2:

Input:nums = [3, 6, 12, 24]

Output:[3, 6, 12, 24]

Explanation:Each number is exactly double the one before it, so every element divides the next — the whole array forms one divisible chain.

Test Case 3:

Input:nums = [3, 4, 16, 8]

Output:[4, 8, 16]

Explanation:Sorted, this is [3, 4, 8, 16]. Starting from 3 only reaches [3] (nothing else is a multiple of 3), while 4 → 8 → 16 chains all the way to length 3 — the better choice.

Constraints

◆1 ≤ nums.length ≤ 10
◆1 ≤ nums[i] ≤ 1000
◆All the integers in nums are distinct
◆If more than one largest divisible subset exists, return the one built by sorting nums ascending first and always preferring the smallest-index predecessor whenever two predecessors would extend a chain to the same length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Sort the array first, since any divisible chain must appear in increasing order once sorted — a later, larger multiple can only ever divide evenly by an earlier, smaller factor. For each starting index, recursively try every later index that the current number divides evenly into, chase the longest chain reachable from there, and prepend the current number to whatever comes back. Repeating that from every possible starting index and keeping the longest result overall finds the answer, but the same "best chain starting here" question gets solved again from scratch every time a different earlier chain happens to reach the same index.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int[] largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        List<Integer> best = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> candidate = solve(i);
            if (candidate.size() > best.size()) best = candidate;
        }
        int[] out = new int[best.size()];
        for (int k = 0; k < out.length; k++) out[k] = best.get(k);
        return out;
    }

    private List<Integer> solve(int i) {
        List<Integer> best = new ArrayList<>();
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] % nums[i] == 0) {
                List<Integer> candidate = solve(j);
                if (candidate.size() > best.size()) best = candidate;
            }
        }
        List<Integer> result = new ArrayList<>();
        result.add(nums[i]);
        result.addAll(best);
        return result;
    }
}

Optimal — Bottom-Up DP with Parent Pointers

Optimal

Sort the array first, for the same reason as above — once sorted, a divisible chain is automatically an increasing sequence, so this becomes the Longest Increasing Subsequence pattern with "nums[i] % nums[j] == 0" in place of "nums[j] < nums[i]". Let dp[i] hold the length of the best divisible chain ending at index i: check every earlier index j, and whenever nums[i] divides evenly by nums[j], dp[i] can extend dp[j] by one. A parent[i] array records which earlier index produced that best length, updating only on a strict improvement so the first qualifying predecessor at a given length wins ties. The index with the largest dp value marks where the answer ends, and walking parent pointers back from there — filling a result array from its last slot toward its first — rebuilds the actual chain in one pass.

TimeO(n²)