# Not best, but interesting, Golang, O(n^2) time on worst case, O(n) space

• the basic idea is that creating a tree, each path in the tree is a subset of numbers satisfying the condition.
The case [1,2,3,4,5,6,24], it will create a tree:

``````1 ---> 2 ------> 4 --------|
|     |                  \|/
|     \-------> 6 -----> 24
|---> 3--------/|\
|-> 5
``````

and find the longest path(s), so the result should be [1,2,4,24] OR [1,2,6,24] OR [1,3,6,24]

``````

import "sort"
import "fmt"

type Node struct{
val int
children []*Node
}

//remove cycle
return
}
//assumed v % n.val ==0
count := 0
for _,c := range n.children{
if toAdd.val % c.val == 0{
count+=1
}
}
if count > 0{
return
}
}

func visit(n *Node, path []int) ([]int, []int){
path = append(path, n.val)
var ret []int = nil
if len(n.children)==0{
//leaf
ret = make([]int, len(path))
copy(ret, path)
}else{
for _,c := range n.children{
var r []int = nil
path,r =  visit(c, path)
if ret==nil || len(r)>len(ret){
ret = make([]int, len(r))
copy(ret, r)
}
}
}
path = path[:len(path)-1]
return path,ret
}

func largestDivisibleSubset(nums []int) []int {
if len(nums)==0{
return nil
}
sort.Ints(nums)
hasOne := nums[0]==1
root := &Node{1, make([]*Node,0)}
i := 0
if hasOne{
i =1
}
for ;i<len(nums);i++{
}

//find the lognest path
_,ret := visit(root, make([]int,0))
if !hasOne{
return ret[1:]
}
return ret
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.