LeetCode 368.

package lc_368;

import java.util.*;

public class Solution {

    List<Integer> max;
    int[] dp;

    public List<Integer> largestDivisibleSubset(int[] nums) {
        max = new ArrayList<>();
        dp=new int[nums.length];
        Arrays.sort(nums);
        Arrays.fill(dp,-1);
        recur(nums, 0, new ArrayList<>());
        return max;
    }

    public void recur(int[] nums, int index, List<Integer> current){
        if (index >= nums.length){
            if (current.size() > max.size()){
                max.clear();
                max.addAll(current);
            }
            return;
        }
        // Take account of this function while current.size is bigger than maximum size
        // which is calculated before; dp[index] means the maximum size of answer list
        // from nums[0] to nums[index]
        if (current.isEmpty() || (current.size() > dp[index] &&
                nums[index] % current.get(current.size()-1) == 0)){
            dp[index] = current.size();
            current.add(nums[index]);
            recur(nums, index+1, current);
            current.remove(current.size() - 1);
        }
        recur(nums, index+1, current);
    }

}