utilize the transitivity of divisibility, kind of like " Longest Increasing Subsequence" problem

However this one requires you to return the actual subset rather than cardinality of the set,

so you need to do some bookkeeping by using another array.

```
public class Solution {
public int[] largestDivisibleSubset(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
Arrays.sort(nums);
int n = nums.length;
int[] counts = new int[n];// cardinality of subset end with nums[i]
int[] previous = new int[n]; // biggest number (smaller than itself) which is divisible by nums[i]
counts[0] = 1;
previous[0] = -1;
int max = 0;
int maxIndex = -1;
for (int i = 1; i < n; i++) {
max = 0;
maxIndex = -1;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && counts[j] > max) {
max = counts[j];
maxIndex = j;
}
}
counts[i] = max + 1;
previous[i] = maxIndex;
}
max = maxIndex = 0;
for (int i = 0; i < n; i++) {
if (counts[i] > max) {
max = counts[i];
maxIndex = i;
}
}
int[] subset = new int[max];
int index = 0;
//backtrack to get subset
do {
subset[index++] = nums[maxIndex];
maxIndex = previous[maxIndex];
} while (maxIndex != -1);
return subset;
}
}
```