• Time:O(n^2)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
const int n = nums.size();
vector<int> ans;
// sizeEndsAt[i] := largest size ends at nums[i]
vector<int> sizeEndsAt(n, 1);
// prevIndex[i] := the best index s.t.
// 1. nums[i] % nums[prevIndex[i]] == 0 and
// 2. can increase the size of the subset
vector<int> prevIndex(n, -1);
int maxSize = 0;  // max size of the subset
int index = -1;   // track the best ending index

sort(begin(nums), end(nums));

// fix max ending num in the subset first
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j)
if (nums[i] % nums[j] == 0 && sizeEndsAt[i] < sizeEndsAt[j] + 1) {
sizeEndsAt[i] = sizeEndsAt[j] + 1;
prevIndex[i] = j;
}
// find a new subset that has a bigger size
if (maxSize < sizeEndsAt[i]) {
maxSize = sizeEndsAt[i];
index = i;  // update the best ending index
}
}

// loop from back to front
while (index != -1) {
ans.push_back(nums[index]);
index = prevIndex[index];
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
final int n = nums.length;
List<Integer> ans = new ArrayList<>();
// sizeEndsAt[i] := largest size ends at nums[i]
int[] sizeEndsAt = new int[n];
// prevIndex[i] := the best index s.t.
// 1. nums[i] % nums[prevIndex[i]] == 0 and
// 2. can increase the size of the subset
int[] prevIndex = new int[n];
int maxSize = 0; // max size of the subset
int index = -1;  // track the best ending index

Arrays.fill(sizeEndsAt, 1);
Arrays.fill(prevIndex, -1);
Arrays.sort(nums);

// fix max ending num in the subset first
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j)
if (nums[i] % nums[j] == 0 && sizeEndsAt[i] < sizeEndsAt[j] + 1) {
sizeEndsAt[i] = sizeEndsAt[j] + 1;
prevIndex[i] = j;
}
// find a new subset that has a bigger size
if (maxSize < sizeEndsAt[i]) {
maxSize = sizeEndsAt[i];
index = i; // update the best ending index
}
}

// loop from back to front
while (index != -1) {
index = prevIndex[index];
}

return ans;
}
}
``````

## Python

``````class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = []
count = [1] * n
prevIndex = [-1] * n
maxCount = 0
index = -1

nums.sort()

for i, num in enumerate(nums):
for j in reversed(range(i)):
if num % nums[j] == 0 and count[i] < count[j] + 1:
count[i] = count[j] + 1
prevIndex[i] = j
if count[i] > maxCount:
maxCount = count[i]
index = i

while index != -1:
ans.append(nums[index])
index = prevIndex[index]

return ans
``````