# Largest Divisible Subset LeetCode Solution

Here, We see Largest Divisible Subset LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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.

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]

## Largest Divisible Subset Leetcode SolutionC++

``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int n=nums.size(), maxi=1, num=-1;
vector<int>v;
sort(nums.begin(), nums.end());
vector<int>dp(n, 1);
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(!(nums[i]%nums[j]) && dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
if(maxi<dp[i]){
maxi=dp[i];
}
}
}
}
for(int i=n-1; i>=0; i--){
if(maxi==dp[i] && (num==-1 || !(num%nums[i]))){
v.push_back(nums[i]);
maxi--;
num=nums[i];
}
}
return v;
}
};```Code language: PHP (php)```

## Largest Divisible Subset Leetcode SolutionJava

``````class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
Arrays.sort(nums);
int maxSize = 1, maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
}
}
List<Integer> result = new ArrayList<>();
int num = nums[maxIndex];
for (int i = maxIndex; i >= 0; i--) {
if (num % nums[i] == 0 && dp[i] == maxSize) {
num = nums[i];
maxSize--;
}
}
return result;
}
}```Code language: PHP (php)```

## Largest Divisible Subset SolutionJavaScript

``````var largestDivisibleSubset = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const dp = new Array(n).fill(1);
let maxSize = 1, maxIndex = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] % nums[j] === 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
}
}
const result = [];
let num = nums[maxIndex];
for (let i = maxIndex; i >= 0; i--) {
if (num % nums[i] === 0 && dp[i] === maxSize) {
result.push(nums[i]);
num = nums[i];
maxSize--;
}
}
return result;
};```Code language: JavaScript (javascript)```

## Largest Divisible Subset SolutionPython

``````class Solution(object):
def largestDivisibleSubset(self, nums):
nums.sort()
n = len(nums)
dp = [1] * n
max_size, max_index = 1, 0
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0:
dp[i] = max(dp[i], dp[j] + 1)
if dp[i] > max_size:
max_size = dp[i]
max_index = i
result = []
num = nums[max_index]
for i in range(max_index, -1, -1):
if num % nums[i] == 0 and dp[i] == max_size:
result.append(nums[i])
num = nums[i]
max_size -= 1
return result``````
Scroll to Top