代码随想录算法训练营第二十三天 | 39、40、131

算法
, , ,

39. 组合总和

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
package main

import "sort"

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates) // 首先对候选数组进行排序，便于后续剪枝和避免重复组合
    var result [][]int    // 存储最终结果的二维切片
    var backtrack func(int, int, []int)

    backtrack = func(start, currentSum int, path []int) {
        for i := start; i < len(candidates); i++ {
            num := candidates[i]
            newSum := currentSum + num

            if newSum > target {
                // 当前和加上候选数超过目标值，由于数组已排序，后续元素更大，直接剪枝
                break
            } else if newSum == target {
                // 找到有效组合，复制当前路径并添加当前数，然后加入结果集
                temp := make([]int, len(path))
                copy(temp, path)
                temp = append(temp, num)
                result = append(result, temp)
                break // 后续元素更大，无需继续循环
            } else {
                // 继续递归探索，允许重复选择当前元素，因此下一轮的起始索引仍为 i
                backtrack(i, newSum, append(path, num))
            }
        }
    }

    backtrack(0, 0, []int{}) // 初始调用，从索引 0 开始，当前和为 0，路径为空
    return result
}

40. 组合总和 II

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
package main

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates) // 排序以方便剪枝和去重
    var res [][]int
    var backtrack func(start, currentSum int, path []int)

    backtrack = func(start, currentSum int, path []int) {
        for i := start; i < len(candidates); i++ {
            // 跳过同一层中重复的元素
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            num := candidates[i]
            sum := currentSum + num
            if sum > target { // 剪枝：后续元素更大，无需继续
                break
            }
            if sum == target { // 找到有效组合
                newPath := make([]int, len(path)+1)
                copy(newPath, path)
                newPath[len(path)] = num
                res = append(res, newPath)
                break // 后续元素更大，无需继续循环
            } else { // 继续探索
                backtrack(i+1, sum, append(path, num))
            }
        }
    }

    backtrack(0, 0, []int{})
    return res
}

131. 分割回文串

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
39
package main

func partition(s string) [][]string {
    var result [][]string
    n := len(s)

    // 判断子串是否为回文
    isPalindrome := func(left, right int) bool {
        for left < right {
            if s[left] != s[right] {
                return false
            }
            left++
            right--
        }
        return true
    }

    var backtrack func(int, []string)
    backtrack = func(start int, path []string) {
        if start >= n { // 到达字符串末尾，保存有效分割方案
            temp := make([]string, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }

        for i := start; i < n; i++ { // 枚举所有可能的结束位置
            if isPalindrome(start, i) {
                // 截取回文子串并继续递归
                backtrack(i+1, append(path, s[start:i+1]))
            }
        }
    }

    backtrack(0, []string{})
    return result
}