# Largest Divisible Subset Problem

## Description

LeetCode Problem 368.

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:

``````1
2
3
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
``````

Example 2:

``````1
2
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
``````

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10^9
• All the integers in nums are unique.

## Sample C++ Code

Dynamic programming approach:

1. We first sort the array so that we only have to check A[i] % A[j] when j < i.
2. The vector dp[i] is the longest subset that satisfies the required conditions and ending at index i. The initial length of any subset is 1.
3. The vector previous_index[i] stores the indices of previously included elements in this subset.
4. For j < i < n, if A[i] % A[j] == 0 and dp[i] < dp[j] + 1, we add A[i] to the subsets that have last element as A[j].
``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& A) {
int n = A.size();

if(n == 0) return {};

sort(A.begin(), A.end());

vector<int> dp(n, 1);
vector<int> previous_index(n, -1);

int max_ind = 0;

for(int i=1; i<n; i++) {
for(int j=0; j<i; j++) {
if(A[i]%A[j]==0 and dp[i] < dp[j] + 1) {
dp[i] = dp[j]+1;
previous_index[i] = j;
}
}
if(dp[i] > dp[max_ind]) {
max_ind = i;
}
}

int t = max_ind;
while(t >= 0) {
t = previous_index[t];
}

}
};
``````