# Missing test case "368. Largest Divisible Subset"

• [3 4 16 8]
in this case, the smallest number 3 is not in the result list [4 16 8]

• The answer for [3, 4, 6, 8] is either [3, 6] or [4, 8]. What do you mean?

• @1337c0d3r
Sorry, it's typo. [3 4 8 16], or [3 4 16 8].
This code is correct.

``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n = nums.size();
if (n <= 1) {
return nums;
}
vector<int> sum(n, 0);
vector<int> best;
int maxL = 0;
sort(nums.begin(), nums.end());
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (!(nums[j] % nums[i])) {
sum[i] = max(sum[i], sum[j] + 1);
maxL = max(maxL, sum[i]);
}
}
}
int i = 0;
while (maxL >= 0) {
if (sum[i] == maxL) {
best.push_back(nums[i]);
maxL--;
int j = i;
while (++j < n && (nums[j] % nums[i] || sum[j] != maxL)) ;
i = j;
} else {
i++;
}
}
return best;
}
};
``````

while this one is wrong, because it cannot pass the case I listed, but it can be accepted.

``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n = nums.size();
if (n <= 1) {
return nums;
}
vector<int> sum(n, 0);
vector<int> best;
int maxL = 0;
sort(nums.begin(), nums.end());
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (!(nums[j] % nums[i])) {
sum[i] = max(sum[i], sum[j] + 1);
maxL = max(maxL, sum[i]);
}
}
}
int i = 0;
while (maxL >= 0) {
if (sum[i] == maxL) {
best.push_back(nums[i]);
maxL--;
int j = i;
while (++j < n && (nums[j] % nums[i] || sum[j] != maxL)) ;
i = j;
}
}
return best;
}
};
``````

• [3 4 16 8]

Got it. I have just added this test case.

Thanks for making LeetCode better. :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.