What is the brute force approach and complexity for Largest Divisible Subset?

Take or skip each number, then check every pair in each set with time complexity O(2^N · N^2) and space complexity O(N).

What is the optimal approach and complexity for Largest Divisible Subset?

Sort; len[i] is the best chain ending at nums[i]; keep parents and walk back with optimal time complexity O(N^2) and space complexity O(N).

How do you identify the pattern for Largest Divisible Subset?

Look for key signals in the prompt: "largest subset" indicates We want a size. Keep the best size for each ending number, and take the maximum at the end.; "every pair has one that divides the other" indicates A group is a chain where each number is a multiple of the one before it. The state only needs the last number.; "distinct positive numbers" indicates No repeats, so each divisor is smaller than the number it divides. Sorting turns the list into a line we can scan..

Largest Divisible Subset

Medium·LeetCode #368Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLIS-style DP with a custom 'can follow' rule: chains and reconstruction

Complexity:O(2^N · N^2)→O(N^2)

Key Insight

Sort the numbers. Let len[i] be the size of the largest valid group whose largest number is nums[i]. For each earlier j, if nums[i] % nums[j] == 0, the group ending at nums[j] can be extended by nums[i]. Keep the best one, and store its parent j. Walking the parents back from the best end gives the group.

Core Validity Invariant

A group is valid when each number divides the next one. Divisibility passes along a chain (if a | b and b | c, then a | c), so every pair in the group divides one way round.

Problem

You get a list of distinct positive whole numbers. Pick the largest group you can from the list, where every two numbers in the group have one that divides the other.

Return any group of the largest size. The order of the numbers in the answer does not matter.

Input

nums, a list of distinct positive whole numbers. The list is not sorted.

Output

A largest group of numbers from nums where every pair has one number dividing the other.

Example 1

Input: nums = [1, 2, 3]

Output: [1, 2]

[1, 3] is also accepted. 2 and 3 do not divide each other, so they cannot both be in the group.

Example 2

Input: nums = [1, 2, 4, 8]

Output: [1, 2, 4, 8]

Each number divides the next one, so all four numbers fit in the group.

Constraints

• 1 ≤ nums.length ≤ 1000
• 1 ≤ nums[i] ≤ 2 · 10^9
• All the integers in nums are unique.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Can 2 and 3 both be in the group? What about 2 and 4? What is the rule for a pair?
2.
Does the order of the numbers in the list help me check the rule? What order would make it easier?
3.
If I know the best group that ends with a number x, how can I use it for a bigger number y?
4.
When I add y to a group, do I have to check y against every number already in the group, or is one check enough?
5.
I know the length of the best group. How do I get the actual numbers back?

Brute force approach

Idea

Each number is either taken or skipped, so there are 2^N sets. For each set, check every pair: one number must divide the other. Keep the largest set that passes.

Thinking process

1
Take [2, 3, 4]. The set {2, 4} is valid: 4 % 2 = 0, so 2 divides 4. Its size is 2.
2
The set {2, 3} is not valid: 3 % 2 = 1 and 2 % 3 = 2, so neither divides the other.
3
The set {2, 3, 4} is not valid either, because it contains the bad pair {2, 3}.
4
Check all 8 sets the same way. The largest valid one is {2, 4}, so the answer has size 2.

Visual

Each circle is one call and shows the numbers picked so far. Blue = the path to the current call. Red = a set that breaks the rule, checked at the bottom. Green = a valid set that is not the best. Purple = the best set so far.

Brute force: every subsetnums = [2, 3, 4]step 1/16

calls

State

picked: none
calls: 1
best size: 0

Next number: 2

Two choices for 2: skip it, or take it. Each choice is one more call.

Code & Implementation

brute.cpp

class Solution {
    // Take or skip each number. At the end, check the pick: every pair must divide one way round.
    bool isChain(const vector<int>& pick) {
        for (size_t a = 0; a < pick.size(); a++)
            for (size_t b = a + 1; b < pick.size(); b++)
                if (pick[a] % pick[b] != 0 && pick[b] % pick[a] != 0) return false;
        return true;
    }

    void go(vector<int>& nums, int i, vector<int>& pick, vector<int>& best) {
        if (i == (int)nums.size()) {
            if (isChain(pick) && pick.size() > best.size()) best = pick;
            return;
        }
        go(nums, i + 1, pick, best);       // skip nums[i]
        pick.push_back(nums[i]);           // take nums[i]
        go(nums, i + 1, pick, best);
        pick.pop_back();                   // undo, so the caller sees its own pick again
    }

public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> pick, best;
        go(nums, 0, pick, best);
        return best;
    }
};

Complexity

Time O(2^N · N^2)Space O(N)

There are 2^N sets, because each number is taken or skipped. Checking one set means looking at every pair, which is about N²/2 pairs. The space is the recursion depth, N, plus the set being built. With N = 1000 this is far too slow; it only works for about 15 numbers.

Optimized approach

Idea

Start from brute force

Brute force tries every set and checks every pair inside it. Many sets share the same numbers, so the same pairs are checked again and again. Instead, keep one best answer for each number, and build it from the numbers before it.

Find the repeated work

A pair of numbers is checked inside every set that contains both. For N = 10, one pair is checked in 2^8 = 256 of the 1024 sets.

Define the state — what variables do I need?

len[i]: The size of the largest valid group whose largest number is `nums[i]` (after sorting).
parent[i]: The index of the number before `nums[i]` in that group, or -1 if `nums[i]` starts the group.
i, j: `i` is the number being filled. `j` is an earlier number that might divide it.

Define validity

A group is valid when each number divides the next one. Divisibility passes along a chain (if a | b and b | c, then a | c), so every pair in the group divides one way round.

Define the transitions — when does each pointer move, and why is it safe?

Once, before the loops

sort(nums)

After sorting, a divisor is always before the number it divides, so every chain can be built from left to right.

For each i, and each earlier j

if nums[i] % nums[j] == 0 and len[j] + 1 > len[i]: set len[i] = len[j] + 1 and parent[i] = j

Every number in the group ending at nums[j] divides nums[j], and nums[j] divides nums[i]. So adding nums[i] keeps the group valid, and only the last number needs checking.

After all the loops

Start at the index with the largest len. Walk parent back to -1, then reverse.

The walk visits exactly the numbers of that group, so reversing gives them in increasing order.

What does the current window add to the answer?

After row i, len[i] is the size of the best valid group that ends with nums[i]. The answer is the largest len, and its parent chain gives the group.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        // Sorted, so a divisor always comes before the numbers it divides.
        sort(nums.begin(), nums.end());
        int n = nums.size();

        // len[i]: size of the best chain that ends with nums[i] (its largest number).
        // parent[i]: the number before nums[i] in that chain, or -1 if the chain starts at nums[i].
        vector<int> len(n, 1), parent(n, -1);
        int bestEnd = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Only the last number of the chain is checked: every earlier number divides nums[j],
                // so it divides nums[i] too.
                if (nums[i] % nums[j] == 0 && len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    parent[i] = j;
                }
            }
            if (len[i] > len[bestEnd]) bestEnd = i;
        }

        // Walk back from the best end, then reverse so the chain is in increasing order.
        vector<int> out;
        for (int k = bestEnd; k != -1; k = parent[k]) out.push_back(nums[k]);
        reverse(out.begin(), out.end());
        return out;
    }
};

Complexity

Time O(N^2)Space O(N)

Sorting costs O(N log N), which is smaller. The double loop checks each pair (j, i) once, so about N²/2 modulo checks. The arrays len and parent hold N values each.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Take or skip each number, then check every pair in each set	O(2^N · N^2)	O(N)
Optimal	Sort; len[i] is the best chain ending at nums[i]; keep parents and walk back	O(N^2)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“largest subset”We want a size. Keep the best size for each ending number, and take the maximum at the end.
“every pair has one that divides the other”A group is a chain where each number is a multiple of the one before it. The state only needs the last number.
“distinct positive numbers”No repeats, so each divisor is smaller than the number it divides. Sorting turns the list into a line we can scan.

Chain in sorted order+each element extends a smaller element+maximum length, with parents to rebuild it→LIS-style DP with a custom 'can follow' rule: chains and reconstruction

This is LIS where the rule is divisibility instead of 'bigger'. In LIS, any bigger number can follow. Here a number can follow only when it is a multiple of the one before, which is a modulo test. The chain property is what makes the O(N²) loop correct: once the list is sorted, checking the last number of a chain is enough, and parent pointers rebuild the group.

Don't make this mistake

Pattern confusion: not sorting first

✗ for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (nums[i] % nums[j] == 0) ... // on the unsorted list

✓ sort(nums.begin(), nums.end()); // then the same two loops

The loop only looks left, so a divisor placed after its multiple is never used. On [4, 2, 1], the loop never links 1 to 2 or 4, so it returns 1. The right answer is 3, the chain [1, 2, 4]. Sorting puts every divisor before the numbers it divides.

Checking only the smallest number

✗ if (x % nums[0] == 0) keep x; // every number is checked against the smallest one

✓ if (x % last == 0) extend the chain ending at last; // check against the chain's last number

Dividing the smallest number is not enough to form a chain. On [1, 2, 3], every number is a multiple of 1, so this keeps all three. But 2 and 3 do not divide each other, so the right answer has size 2, for example [1, 2].

Returning the chain that ends at the last number

✗ return the chain that ends at nums[n - 1];

✓ return the chain that ends at the index with the largest len[i];

The best group does not have to end at the largest number. On [1, 2, 4, 8, 9], the chain ending at 9 is just [1, 9] (size 2). The best group is [1, 2, 4, 8] (size 4).

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture