Can any one share how you come up with your recurrence formula?

 sort the array first to make it easier to consider next move
 every pair of numbers in a set should be divisible by the larger one and now since it's sorted, so the larger one is the one with higher index
 traversing the sorted array and record the maximal amount of the set ending with the current number is the key.
when doing this, we should check if there are subsets available before for the current number (which can divide the current  which we can add the current to the subset to make a larger subset) and then update the max amount for the current number 
 meantime to be able to collect the subsets later on, we should record the previous index of the smaller number and also we should update the global max till the end.
A solution in C++ should be like this.
class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { int size = nums.size(); if(!size) return vector<int>(); sort(nums.begin(), nums.end()); vector<pair<int, int>> maxWithIndex(1, make_pair(1, 1)); int globalMax = 1, index = 0; for(int i = 1; i < size; ++i) { int maxCount = 1, preIndex = 1; for(int j = i1; j >=0; j) { if(nums[i]%nums[j]==0 && maxWithIndex[j].first>=maxCount) maxCount = maxWithIndex[j].first+1, preIndex = j; } maxWithIndex.emplace_back(maxCount, preIndex); if(maxCount > globalMax) globalMax = maxCount, index = i; } vector<int> v; for(int i = 0; i < globalMax; ++i, index = maxWithIndex[index].second) v.insert(v.begin(), nums[index]); return v; } };