leetcode-sol/39.CombinationSum.go at master · kohn/leetcode-sol · GitHub

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
package main
import (
        "fmt"
)

func combinationSum(candidates []int, target int) [][]int {
        solutions := make([][]int, 0)
        if target <= 0 || len(candidates) == 0{
                return solutions
        }

        if len(candidates) == 1 && target == candidates[0] {
                return [][]int{candidates}
        }

        for i:=0;i<len(candidates);i++{
                if candidates[i] <= target {
                        if target - candidates[i] == 0 {
                                solutions = append(solutions, []int{candidates[i]})
                        } else {
                                sol := combinationSum(candidates[i:], target-candidates[i])
                                for _, s := range sol {
                                        if len(s) > 0 {
                                                solutions = append(solutions, append(s, candidates[i]))
                                        }
                                }
                        }
                }
        }
        return solutions
}


func main() {
        result := combinationSum([]int{2, 3, 5}, 8)
        fmt.Println(result)
}