Contents

# Problem

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

\$\$S_i \bmod S_j = 0\$\$ or \$\$S_j \bmod S_i = 0\$\$.

If there are multiple solutions, return any subset is fine.

## example 1

 ``````1 2 `````` ``````Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) ``````

## example 2

 ``````1 2 `````` ``````Input: [1,2,4,8] Output: [1,2,4,8] ``````

# Solution

## HashMap

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 `````` ``````func largestDivisibleSubset(nums []int) []int { haveOne := false sort.Ints(nums) q := make(map[int][]int, 0) for idx :=range nums { if nums[idx] == 1 { haveOne = true continue } q[nums[idx]] = []int{} for jdx:=idx+1; jdxlen(w) { w = res } } if haveOne { return append([]int{1}, w...) } return w } func helper(q map[int][]int, idx int) []int { if _, ok := q[idx]; !ok { return []int{} } if len(q[idx]) == 0 { return []int{idx} } tmp := []int{} for jdx := range q[idx] { w := helper (q, q[idx][jdx]) if len(w) == len(q[idx]) { return append([]int{idx}, w...) } if len(w)>len(tmp) { tmp = w } } return append([]int{idx}, tmp...) } ``````