# Leetcode Largest Divisible Subset problem solution

In this Leetcode Largest Divisible Subset problem solution You are 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:

If there are multiple solutions, return any of them.

## Problem solution in Python.

```class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:

n=len(nums)
#base case
if n==1 or n==0:
return nums
#sorting to apply lis
nums.sort()

#DP table
lis=[1 for _ in range(n)]

#table to store indexes
pre=[-1 for _ in range(n)]

max=0
index=-1
for i in range(0,n):
for j in range(i-1,-1,-1):
if nums[i]%nums[j]==0:
if lis[i]<lis[j]+1:
lis[i]=lis[j]+1
pre[i]=j
if lis[i]>max:
max=lis[i]
index=i

subset=[]
while index!=-1:
subset.insert(0,nums[index])
index=pre[index]

return subset
```

## Problem solution in Java.

```public List<Integer> largestDivisibleSubset(int[] nums) {

List<Integer> ret = new ArrayList<Integer>();

if (nums == null || nums.length == 0)
return ret;

Arrays.sort(nums);

int[] dp = new int[nums.length];
int[] prev = new int[nums.length];
Arrays.fill(dp, 1);
prev[0] = 0;

for (int i = 1; i < nums.length; i++) {
for (int j = i-1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {

if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}

}
}
}
int maxIndex = 0;
for (int i = 0; i < dp.length; i++) {
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}

int len = dp[maxIndex];

while (true) {
maxIndex = prev[maxIndex];

if (--len <= 0)
break;
}

return ret;

}
```

## Problem solution in C++.

```class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n = nums.size();
if(n == 0) {
return vector<int>();
}
vector<int> dp(n, 1);
vector<int> parent(n, -1);
sort(nums.begin(), nums.end());
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
}
int maxIndex = 0, maxLen = 0;
for(int i=0;i<n;i++) {
if(dp[i] > maxLen) {
maxLen = dp[i];
maxIndex = i;
}
}
vector<int> ans(maxLen);
int x = maxLen-1;
while(maxIndex != -1) {
ans[x] = nums[maxIndex];
maxIndex = parent[maxIndex];
x--;
}
return ans;
}
};
```

## Problem solution in C.

```int cmp(void* a,void* b){
return *(int*)a-*(int*)b;
}
void func(int* nums, int numsSize,int* map,int* lens,int pre_index){
if(numsSize==1||map[0]!=0){
return;
}
for(int i=1;i<numsSize;i++){
if(nums[i]%nums[0]==0){
if(map[i]==0){
func(&nums[i], numsSize-i,&map[i],&lens[i],pre_index+i);
}
if(lens[0]<lens[i]+1){
map[0]=i+pre_index;
lens[0]=lens[i]+1;
}
}
}
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
*returnSize=0;
if(numsSize==0){
return NULL;
}
qsort(nums,numsSize,sizeof(nums[0]),cmp);
int* map=(int*)calloc(numsSize,sizeof(int));
int* lens=(int*)calloc(numsSize,sizeof(int));
int* ret=(int*)calloc(numsSize,sizeof(int));
for(int i=0;i<numsSize-1;i++){
if(map[i]!=0){
continue;
}
func(&nums[i], numsSize-i,&map[i],&lens[i],i);
}
int index=0;
for(int i=1;i<numsSize;i++){
if(lens[i]>lens[index]){
index=i;
}
}
while(map[index]!=0){
ret[(*returnSize)++]=nums[index];
index=map[index];
}
ret[(*returnSize)++]=nums[index];
return ret;
}
```