Sponsored
Sponsored
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.
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5vector<int> largestDivisibleSubset(vector<int>& nums) {
6 if (nums.empty()) return {};
7 sort(nums.begin(), nums.end());
8 int n = nums.size();
9 vector<int> dp(n, 1), previous(n, -1);
10 int maxSize = 1, maxIndex = 0;
11 for (int i = 1; i < n; ++i) {
12 for (int j = 0; j < i; ++j) {
13 if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
14 dp[i] = dp[j] + 1;
15 previous[i] = j;
16 }
17 }
18 if (dp[i] > maxSize) {
19 maxSize = dp[i];
20 maxIndex = i;
21 }
22 }
23 vector<int> result;
24 for (int i = maxIndex; i >= 0; i = previous[i])
25 result.push_back(nums[i]);
26 reverse(result.begin(), result.end());
27 return result;
28}The C++ solution is similar to the C solution, using vectors and the sort function for sorting. It leverages two primary vectors, dp to track subset sizes and previous for backtracking. As elements are iterated, the logic for updating dp[i] and previous[i] is executed using nested loops. The largest subset is determined and reconstructed by tracking indices with the help of the previous vector.
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.
...