跳转至

LC39 - 组合总和

CombinationSum.go
 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
package Backtrack

import (
    "cmp"
    "slices"
)

func combinationSum(candidates []int, target int) [][]int {
    slices.SortFunc(candidates, func(a, b int) int {
        return cmp.Compare(b, a)
    })
    size := len(candidates)
    result := make([][]int, 0)
    path := make([]int, 0)
    pathSum := 0
    var f func(i int)
    f = func(i int) {
        if i == size || pathSum > target {
            return
        }
        if pathSum == target {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
            return
        }
        // (1) 不选择当前元素
        f(i + 1)
        // (2) 选择一个当前元素
        path = append(path, candidates[i])
        pathSum += candidates[i]
        f(i)
        path = path[:len(path)-1]
        pathSum -= candidates[i]
    }
    f(0)
    return result
}