54 lines
991 B
Go
54 lines
991 B
Go
package top100liked
|
|
|
|
import (
|
|
"fmt"
|
|
"testing"
|
|
)
|
|
|
|
// https://leetcode.cn/problems/combination-sum/?envType=study-plan-v2&envId=top-100-liked
|
|
|
|
func combinationSum(candidates []int, target int) [][]int {
|
|
res := [][]int{}
|
|
sum := 0
|
|
r := []int{}
|
|
|
|
var helper func(strat int)
|
|
helper = func(start int) {
|
|
for i := start; i < len(candidates); i++ {
|
|
v := candidates[i]
|
|
if sum+v == target {
|
|
cp := make([]int, len(r))
|
|
copy(cp, r)
|
|
cp = append(cp, v)
|
|
res = append(res, cp)
|
|
continue
|
|
} else if sum+v < target {
|
|
r = append(r, v)
|
|
sum += v
|
|
helper(i)
|
|
sum -= v
|
|
r = r[:len(r)-1]
|
|
}
|
|
}
|
|
}
|
|
|
|
helper(0)
|
|
return res
|
|
}
|
|
|
|
func Test(t *testing.T) {
|
|
fmt.Printf("%+v\n", combinationSum([]int{2, 3, 6, 7}, 7))
|
|
}
|
|
|
|
func Test2(t *testing.T) {
|
|
fmt.Printf("%+v\n", combinationSum([]int{2, 3, 5}, 8))
|
|
}
|
|
|
|
func Test3(t *testing.T) {
|
|
fmt.Printf("%+v\n", combinationSum([]int{2}, 1))
|
|
}
|
|
|
|
func Test4(t *testing.T) {
|
|
fmt.Printf("%+v\n", combinationSum([]int{4, 2, 8}, 8))
|
|
}
|