LeetCode 39. 组合总和

Categories:

Tags:

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

题目描述

✅ 39. 组合总和

思路分析

思路描述

参考代码

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

	var backtrack func(start, curSum int)

	backtrack = func(start, curSum int) {
		if curSum == 0 {
			res = append(res, append([]int{}, path...))
			return
		}

		for i := start; i < len(candidates); i++ {
			if candidates[i] > curSum {
				continue
			}

			path = append(path, candidates[i])
			backtrack(i, curSum-candidates[i])
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)

	return res
}

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

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

		// 遍历 candidates 数组中的每个数
		for i := start; i < len(candidates); i++ {
			// 剪枝：如果当前数已经大于 target，直接跳出
			if candidates[i] > target {
				continue
			}
			// 选择当前数
			path = append(path, candidates[i])
			// 递归选择下一个数
			backtrack(i, target-candidates[i])
			// 回溯，移除当前数
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return res
}

时间复杂度：O(2^n)

空间复杂度：O(target)

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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