368 Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine.
Example 1:

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]
Result: [1,2,4,8]

Solution

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size(), lmax = 1;
        vector<int> tmp;
        if ( n == 0 ) return tmp;
        vector<vector<int>> res(n, tmp);
        sort(nums.begin(), nums.begin()+n);
        tmp.push_back(nums[0]);
        res[0] = tmp;
        for ( int i = 1; i <= n-1; i++ ) {
            int imax = -1, length = 0;
            for ( int j = i-1; j >= 0; j-- ) {
                if ( nums[i]%nums[j] == 0 ) {
                    if ( res[j].size() >= length ) {
                        length = res[j].size();
                        imax = j;
                    }
                }
            }
            if ( imax == -1 ) {
                vector<int> tmp1(1, nums[i]);
                res[i] = tmp1;
            }
            else {
                tmp = res[imax];
                tmp.push_back(nums[i]);
                res[i] = tmp;
                lmax = max(lmax, int(tmp.size()));
            }
        }
        for ( int i = 0; i <= n-1; i++ ) {
            if ( int(res[i].size()) == lmax ) return res[i];
        }
        return res[0];
    }
};

Notes: a little bit smarter than brute-force solution

1. We first sort the given numbers in ascending order. Then we examine the numbers one by one. When adding a new number $$n_1 = nums[i]$$, examine all the numbers $$n_2 = nums[j]$$ ( $$j < i$$ ) that are smaller than $$n_1$$. We use an array of sets $$res$$ to record the solution of sub-problem. $$res[i]$$ represents the largest divisible subset that includes $$nums[i]$$ as the maximum number.
   For example:

   nums = [1, 2, 3, 4, 6, 8]
   res = [[1],
       [1, 2],
       [1, 3],
       [1, 2, 4],
       [1, 3, 6],
       [1, 2, 4, 8]]
   

   Note the following property:
   If $$n_1 = nums[i]$$ is divisible by $$n_2 = nums[j]$$, then $$res[j] + n_1$$ is one possible candidate for $$res[i]$$. This is because if $$n_1 \mod n_2 = 0 $$ and $$n_2 \mod n = 0 $$, then $$n_1 \mod n = 0$$.

2. We traverse $$nums[j], nums[j-1], ......, nums[0]$$ to search for the largest subsets among all the possible candidates.