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.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.
C++
Java
Python
C#
JavaScript
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.
...
C++
Java
Python
C#
JavaScript
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. |
DP 44. Largest Divisible Subset | Longest Increasing Subsequence • take U forward • 151,275 views views
Watch 9 more video solutions →Practice Largest Divisible Subset with our built-in code editor and test cases.
Practice on FleetCode