当前位置：首页 > news >正文

深入解析：【LeetCode 热题100】回溯：括号生成组合总和（力扣22 / 39 ）（Go语言版）

news 2026/6/14 1:36:41

? 回溯专题：括号生成 & 组合总和（LeetCode 22 & 39）

LeetCode 回溯经典题：

22. 括号生成
39. 组合总和

这两道题都考察了回溯算法的剪枝与路径构造能力

? 一、22. 括号生成

? 题目描述

给你一个整数 n，请你生成所有由 n 对括号组成的有效括号组合。

? 示例

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

? 解题思路

这是一道典型的回溯搜索问题，我们通过维护左右括号的使用数量来构造合法的组合。

✅ 回溯核心逻辑：

初始状态：left = 0, right = 0
分支选择：
- 如果 left < n：可以添加 '('
- 如果 right < left：可以添加 ')'
当左右括号都用完（即 left == right == n）时，将当前路径加入结果集。

? Go 实现

func generateParenthesis(n int
) []string {
var res []string
var backtrack func(path string
, left, right int
)
backtrack =
func(path string
, left, right int
) {
if len(path) == 2*n {
res = append(res, path)
return
}
if left < n {
backtrack(path+"("
, left+1
, right)
}
if right < left {
backtrack(path+")"
, left, right+1
)
}
}
backtrack(""
, 0
, 0
)
return res
}

? 二、39. 组合总和

? 题目描述

给你一个无重复正整数数组 candidates，和一个目标整数 target，找出所有可以使数字和为 target 的组合。
每个数可以重复使用无限次。

? 示例

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

? 解题思路

这是标准的回溯 + 剪枝问题，本质是一个组合问题。

✅ 回溯核心逻辑：

状态参数：当前组合 path，当前总和 sum，起始索引 start
分支选择：遍历 candidates[i]，每次可选择当前元素或后面的元素（允许重复选择）
剪枝策略：

? Go 实现

func combinationSum(candidates []int
, target int
) [][]int {
var res [][]int
var path []int
var dfs func(start, sum int
)
dfs =
func(start, sum int
) {
if sum == target {
temp := make([]int
, len(path)
)
copy(temp, path)
res = append(res, temp)
return
}
if sum > target {
return
}
for i := start; i <
len(candidates)
; i++ {
path = append(path, candidates[i]
)
dfs(i, sum + candidates[i]
) // 可重复使用同一个数
path = path[:len(path)-1] // 回溯
}
}
dfs(0
, 0
)
return res
}

⚠️ 注意事项

每层递归都从当前索引 start 开始，确保可以重复选择元素；
注意剪枝时不要提前跳过合法路径；
每次递归完后必须回溯清除最后一个元素。

? 总结与对比

特性	括号生成（22）	组合总和（39）
技巧类型	回溯 + 状态剪枝	回溯 + 剪枝 + 组合
路径构建逻辑	括号平衡 + 左右限制	数组和满足目标
剪枝条件	`right <= left`，括号合法	`sum <= target`
是否可重复选择	否	是
输出顺序	所有合法括号	所有合法组合