Abstract / Summary

Given a set of integers, find the largest subset where each element divides every larger element in the subset.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Math
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation computes a largest subset of a given integer list where every pair of elements satisfies a divisibility relation (for any two numbers a and b in the subset, either a % b == 0 or b % a == 0). It proceeds in three logical phases: sorting the input, building a dynamic-programming table that records the best chain length ending at each possible divisor, and finally reconstructing the actual subset by walking backwards from the highest element of the optimal chain.

Sorting and Initialization

The algorithm begins by sorting the input list, which guarantees that any potential divisor of a number appears earlier in the iteration. The initial dynamic-programming map dp is seeded with a dummy divisor 1 mapped to length 0. Two auxiliary variables, longest and high, keep track of the current maximum chain length and the element that terminates that chain.

dp = {}
dp[1] = 0
longest = 0
high    = 1

for n in sorted(nums):
    ...

By starting with 1, the code ensures that any number can begin a chain, even when the input does not contain 1.

Dynamic-Programming Construction

For each sorted number n, a temporary dictionary add (a defaultdict(int)) records the best chain length that can be achieved by appending n to an existing chain whose last element is a divisor d. The inner loop iterates over all current keys in dp. When n is divisible by d, the candidate length dp[d] + 1 is compared against the current entry for n in add. If it improves the length, add[n] is updated and the global longest and high values are possibly refreshed.

add = defaultdict(int)
for d in dp:
    if n % d == 0 and add[n] < dp[d] + 1:
        add[n] = dp[d] + 1
        if longest < add[n]:
            longest = add[n]
            high    = n

After processing all divisors for the current n, the temporary results are merged back into dp. This incremental update avoids revisiting numbers that have already been processed and keeps the dictionary size bounded by the number of distinct divisors encountered.

for a in add:
    dp[a] = add[a]

Reverse Mapping of Lengths to Values

Once the forward DP table is complete, a reverse mapping reverse is built, grouping numbers by the length of the longest chain that ends with them. This structure enables efficient lookup of candidate numbers when reconstructing the subset.

reverse = defaultdict(set)
for d in dp:
    reverse[dp[d]].add(d)

Using a set for each length eliminates duplicate entries and supports fast membership tests.

Subset Reconstruction

The reconstruction phase walks backward from the recorded high value, which marks the end of the longest chain. For each target length i descending from longest to 1, the algorithm scans the set of numbers that have chain length i. The first number r that divides the current high is selected, appended to the result list, and becomes the new high. The inner break ensures that exactly one element per length is chosen, preserving the divisibility property.

result = []
for i in range(longest, 0, -1):
    for r in reverse[i]:
        if high % r == 0:
            result += [ r ]
            high = r
            break

The final result list contains the elements of the largest divisible subset in descending order, matching the order in which they were discovered during reconstruction.

Edge Cases Handled

When the input list is empty, the sorted iteration yields no numbers, leaving longest at 0. The reconstruction loop runs over an empty range, and the function returns an empty list, correctly representing the absence of any subset.

If the input contains a single element, the DP step will create a chain of length 1 with that element as high. The reverse mapping will contain a single entry for length 1, and the reconstruction loop will select that element, returning a list with the sole number.

Duplicate values in the input are naturally handled because the DP dictionary keys are unique; each distinct number is processed once, and the chain length reflects the best possible inclusion of that value regardless of repetitions.

Numbers that are prime or have no divisors among previously seen elements will not extend any existing chain. In such cases, add remains empty for that iteration, leaving dp unchanged and preserving the current longest and high. This behavior ensures that the algorithm does not mistakenly create invalid chains.

Performance Optimizations

The code leverages several techniques to keep execution efficient. Sorting the input once provides a deterministic order that eliminates the need for repeated divisor searches. The DP dictionary stores only the best length for each divisor, avoiding redundant calculations. Using defaultdict(int) for add and defaultdict(set) for reverse eliminates explicit existence checks and streamlines updates. Merging temporary results into dp after each number prevents the inner loop from seeing partially updated states, which could otherwise increase the number of modulo operations. Finally, the reconstruction loop breaks immediately after finding a suitable divisor, preventing unnecessary scans of the entire set for each length.

Think of this code like playing a game where you collect blocks that fit together perfectly. Imagine you have a big pile of numbered blocks. You want to make a line of blocks where every block can be divided evenly by the one that came before it.

The code starts by sorting all the blocks from smallest to largest so it is easier to look at them. It uses a special notebook to keep track of how many blocks fit in a row for each number. Every time it picks up a new block, it checks if that block can be stacked on top of the ones already in the pile. If the block fits, it remembers that it found a longer chain.

After looking at every block, it searches through its notes to find the very longest chain it created. It starts from the end of the chain and works backward, picking out the pieces that fit until the whole tower is built. By finishing this task, the code reveals the perfect sequence of blocks that all play nicely with each other.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java			TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python			Rust	Java	Go		TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis			JS
	fpdjsns	C++
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	Shamik07								Dart
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality