39-组合总和

题目

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

简单的使用回溯法就行了

/*
 * @lc app=leetcode.cn id=39 lang=golang
 *
 * [39] 组合总和
 */

// @lc code=start
func combinationSum(candidates []int, target int) [][]int {
	// 定义结果集
	res := [][]int{}
	// 定义路径
	path := []int{}
	// 定义回溯函数
	var backtrack func(int, int)
	backtrack = func(target, start int) {
		// 终止条件
		if target < 0 {
			return
		}
		if target == 0 {
			// 注意这里不能直接append(path), 因为path会变化
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}
		// 遍历选择列表
		for i := start; i < len(candidates); i++ {
			// 做选择
			path = append(path, candidates[i])
			// 进入下一层决策树
			backtrack(target-candidates[i], i)
			// 撤销选择
			path = path[:len(path)-1]
		}
	}

	backtrack(target, 0)

	return res
}

// @lc code=end

题目​

题目