Largest Divisible Subset - Solution & Explanation
Problem Statement
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] == 0
If 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 * 109- All the integers in
numsare unique.
Approach Overview
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 1: Dynamic Programming with Sorting
This approach utilizes dynamic programming along with sorting to find the largest subset where each pair of elements is divisible by the other. The core idea is to sort the array, then use a dynamic programming array to keep track of the size of the largest divisible subset that ends at each element. We also maintain a path array to help reconstruct the subset.
This C solution first checks if the input size is zero and returns an empty subset in that case. Otherwise, it sorts the numbers using qsort for processing. It uses a dynamic array, dp, where dp[i] indicates the length of the largest subset that ends with nums[i]. Another array, previous, tracks the path for reconstructing the subset. The nested for-loops store values in dp by checking divisibility and update the maxSize and maxIndex. Finally, the subset is reconstructed from previous and returned.
Complexity
Time Complexity: O(n^2), where n is the number of elements in the input set due to the nested loop.
Space Complexity: O(n), for arrays used to store intermediate results.
Approach 2: Backtracking with Pruning
This approach leverages backtracking with pruning to explore subsets and constrain exploration using the divisibility constraint. It uses a sorted array to systematically explore subsets and prune paths early when constraints are no longer satisfied, allowing potentially faster exploration compared to the dynamic programming approach, especially in tightly constrained subsets.
...
Complexity
Time and space complexities are challenging to define precisely for a backtracking solution as they depend on many factors including input distribution.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(n^2), where n is the number of elements in the input set due to the nested loop. |
| Backtracking with Pruning | Time and space complexities are challenging to define precisely for a backtracking solution as they depend on many factors including input distribution. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Largest Divisible Subset | Dynamic programming | Leetcode #368 • Techdose • 28,133 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Divisible Subset easy or hard?
How to solve Largest Divisible Subset in O(n)?
What is the best approach for Largest Divisible Subset?
Is Largest Divisible Subset asked at Google/Amazon/Meta?
What data structure is used in Largest Divisible Subset?
What is the time complexity of Largest Divisible Subset?
Largest Divisible Subset Python or Java solution approach?
Ready to solve this problem?
Practice Largest Divisible Subset with our built-in code editor and test cases.
Practice on FleetCode