Watch 10 video solutions for Largest Divisible Subset, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by take U forward has 151,275 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
answer[i] % answer[j] == 0, oranswer[j] % answer[i] == 0If there are multiple solutions, return any of them.
Example 1:
Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted.
Example 2:
Input: nums = [1,2,4,8] Output: [1,2,4,8]
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 2 * 109nums are unique.Problem Overview: Given a set of distinct positive integers, return the largest subset where for every pair (a, b), either a % b == 0 or b % a == 0. The task is essentially finding the longest chain where each number divides the next.
Approach 1: Backtracking with Pruning (Exponential Time)
This approach generates subsets using recursive backtracking and keeps only those where every newly added number is divisible with the last chosen element. Sorting the array first helps prune invalid branches early because divisibility relationships become easier to check in order. At each step you either include the current number if it satisfies the divisibility rule or skip it. This brute-force search explores many combinations, resulting in O(2^n) time in the worst case and O(n) recursion space.
Approach 2: Dynamic Programming with Sorting (O(n^2) time)
The optimal solution sorts the array first, which guarantees that if nums[i] % nums[j] == 0 for j < i, then nums[j] can appear before nums[i] in a valid divisible chain. Use a DP array where dp[i] stores the size of the largest divisible subset ending at index i. For each element, iterate through all previous elements and extend the chain if the divisibility condition holds. Maintain a parent array to reconstruct the subset after computing the maximum length. This approach runs in O(n^2) time and requires O(n) extra space for the DP and reconstruction arrays.
The key insight is that after sorting, the problem becomes similar to a longest increasing subsequence variant where the transition condition is divisibility instead of ordering. Each number attempts to extend the best chain formed by smaller numbers.
Core techniques involved include sorting to establish order, dynamic programming for optimal substructure, and simple arithmetic checks from math properties of divisibility.
Recommended for interviews: The dynamic programming with sorting approach is the expected solution. Interviewers want to see recognition of the LIS-style DP pattern and the ability to reconstruct the subset using parent pointers. Backtracking demonstrates baseline reasoning but does not scale well for larger inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(2^n) | O(n) | Useful for understanding subset generation or when input size is very small |
| Dynamic Programming with Sorting | O(n^2) | O(n) | Best general solution for interview settings and typical constraints |