368. Largest Divisible Subset

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]

Credits:Special thanks to @Stomach_ache for adding this problem and creating all test cases.

Solution

import java.util.*;
import java.util.stream.Collectors;
public class Solution {
      public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);

        int size = nums.length;
        Map<Integer, Set<Integer>> map = new HashMap<>();

        Set<Integer> set = new HashSet<>();
        set.add(nums[0]);
        map.put(0, set);

        for (int i = 1; i < nums.length; i++) {
            int current = 1;
            Set<Integer> memorySet = new HashSet<>();
            for (int j = 0; j < i; j++) {
                Set<Integer> currentSet = map.get(j);

                boolean flag = true;
                for (Integer candidate : currentSet) {
                    if (!(candidate % nums[i] == 0 || nums[i] % candidate == 0)) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    if (currentSet.size() + 1 > current) {
                        current = currentSet.size() + 1;
                        memorySet = new HashSet<>(currentSet);
                    }
                }
            }

            memorySet.add(nums[i]);
            map.put(i, memorySet);
        }

        Optional<Set<Integer>> resultSet = map.values().stream().min((a, b) -> b.size() - a.size());
        if (resultSet.isPresent()) {
            return resultSet.get().stream().collect(Collectors.toList());
        } else {
            return result;
        }
    }
}