Find the largest subset of numbers such that every pair is divisible in at least one direction after ordering the subset appropriately.
Given a list of distinct positive integers, return the largest subset such that for every pair of elements in the subset, one number divides the other. If multiple valid subsets have the same maximum size, any one of them may be returned.
A common way to think about the condition is to arrange the chosen numbers in increasing order, where each number divides the next number in the sequence.
Input Format
- An integer array
numsof distinct positive integers. nums[i]represents one candidate number that may be included in the subset.
Output Format
- Return the largest divisible subset as an array of integers.
- The order of returned elements should be increasing or otherwise consistent with divisibility.
Constraints
1 <= nums.lengthnums[i] > 0- All values in
numsare distinct. - The subset must be non-empty.
Example 1
Input
nums = [1,2,3]
Output
[1,2]
Explanation
Both [1,2] and [1,3] are valid largest subsets of size 2.
Example 2
Input
nums = [1,2,4,8]
Output
[1,2,4,8]
Explanation
Each number divides the next one, so the whole array is a valid subset.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.