【代码随想录】算法训练计划27

回溯

1、39. 组合总和

题目：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

思路：

• 第二次写了，很简单就写出来了
• 注意 2 可以使用多次。_backtrack(res, list,candidates, target,sum, i+1),不要i+1

func combinationSum(candidates []int, target int) [][]int {
    // 代码二刷，很经典，回溯
    list := make([]int, 0)
    res := make([][]int, 0)
    backtrack(&res, list,candidates,target,0,0)
    return res
}
func backtrack(res *[][]int, list,candidates []int, target, sum,index int) {
    if sum == target {
        ans := make([]int, len(list))
        copy(ans, list)
        *res = append(*res, ans)
        return
    }
    if sum > target {return}
    for i := index; i<len(candidates); i++ {
        sum += candidates[i]
        list = append(list, candidates[i])
        backtrack(res, list,candidates, target,sum, i)
        sum -= candidates[i]
        list = list[:len(list)-1]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2、40. 组合总和 II

题目：
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

思路：

• 怎么去重呢?，使用 history
• else if sum > target 记得这个也要剪枝，避免无效运算导致的超时

func combinationSum2(candidates []int, target int) [][]int {
    // 代码二刷
    sort.Ints(candidates)
    history := make([]bool, len(candidates))
    list := make([]int, 0)
    res := make([][]int, 0)
    backtrack(&res, list,candidates,target,0,0,history)
    return res
}
func backtrack(res *[][]int, list, candidates []int, target, index, sum int,history []bool) {
    if sum == target {
        ans := make([]int, len(list))
        copy(ans, list)
        *res = append(*res, ans)
        return
    } else if sum > target {
        return
    }
    for i:=index; i<len(candidates); i++ {
        if i>=1 && candidates[i] == candidates[i-1] && history[i-1] == false {
            continue
        }
        sum += candidates[i]
        list = append(list, candidates[i])
        history[i] = true
        backtrack(res, list, candidates, target, i+1, sum,history)
        sum -= candidates[i]
        list = list[:len(list)-1]
        history[i] = false
    }
}
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

3、131. 分割回文串

题目：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

思路：

• 细节，注意：i:=index
• 注意其实回文很简单，带入例子就明白了
• *res = append(*res, ans)，注意是 ans，为什么呢？

func partition(s string) [][]string {
    // 代码二刷，条件就是判断是否为回文字符串
    list := make([]string, 0)
    res := make([][]string, 0)
    backtrack(&res, list, s, 0)
    return res
}
func backtrack(res *[][]string, list []string, s string, index int) {
    if index == len(s) {
        ans := make([]string, len(list))
        copy(ans, list)
        *res = append(*res, ans)
        return
    }
    for i:=index; i<len(s); i++ {
        if huiwen(s, index, i) {
            list = append(list, s[index:i+1])
            backtrack(res, list, s, i+1)
            list = list[:len(list)-1]
        }
    }
}
func huiwen(s string, left,right int) bool {
    for left<right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}
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