this repo has no description
tulkdan.dev
1package main
2
3import "sort"
4
5func dfs(candidates []int, target int, i int, total int, curr []int, res [][]int) [][]int {
6 if total == target {
7 return append(res, curr)
8 }
9
10 if total > target || i >= len(candidates) {
11 return res
12 }
13
14 var newCurr = make([]int, len(curr)+1)
15 copy(newCurr, append(curr, candidates[i]))
16 newRes := dfs(candidates, target, i, total+candidates[i], newCurr, res)
17
18 nextRes := dfs(candidates, target, i+1, total, curr, res)
19
20 return append(newRes, nextRes...)
21}
22
23func combinationSum(candidates []int, target int) [][]int {
24 return dfs(candidates, target, 0, 0, []int{}, [][]int{})
25}
26
27func combinationSum2(candidates []int, target int) [][]int {
28 sort.Ints(candidates)
29
30 result := [][]int{}
31
32 var backtrace func(int, int, []int)
33 backtrace = func(i int, val int, curr []int) {
34 if val == target {
35 result = append(result, append([]int{}, curr...))
36 return
37 }
38
39 if val > target {
40 return
41 }
42
43 for j := i; j < len(candidates); j++ {
44 if j > i && candidates[j] == candidates[j - 1] {
45 continue
46 }
47
48 backtrace(j+1, val + candidates[j], append(curr, candidates[j]))
49 }
50 }
51
52 backtrace(0, 0, []int{})
53
54 return result
55}
56