LeetCode 40. 组合总和 II

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 40. 组合总和 II

思路分析

回溯算法

参考代码

func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var path []int

	// 排序是为了方便剪枝和去重
	sort.Ints(candidates)

	var backtrack func(start int, target int)
	backtrack = func(start, target int) {
		// 如果目标为 0，说明找到了一个组合
		if target == 0 {
			res = append(res, append([]int{}, path...))
			return
		}

		for i := start; i < len(candidates); i++ {
			// 剪枝：如果当前数已经大于 target，直接跳出
			if candidates[i] > target {
				break
			}
			// 去重：跳过同一层中重复的元素
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}

			// 选择当前数
			path = append(path, candidates[i])

			// 递归，注意 i+1 表示不能重复使用当前数字
			backtrack(i+1, target-candidates[i])

			// 回溯
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/90779862