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.
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.
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.
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.
...
Time and space complexities are challenging to define precisely for a backtracking solution as they depend on many factors including input distribution.
| 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 | — |
| 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 |
DP 44. Largest Divisible Subset | Longest Increasing Subsequence • take U forward • 206,407 views views
Watch 9 more video solutions →Practice Largest Divisible Subset with our built-in code editor and test cases.
Practice on FleetCode