面试腾讯算法:组合总和

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

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

 

方法:搜索回溯

//一个dfs里面调用2个dfs函数,这样的递归形成了一个类似树的结构
func combinationSum(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	
	var dfs func(target, idx int)
	
	dfs = func(target, idx int) {
		//idx表示遍历到的下标
		if idx == len(candidates) {
			return
		}
		
		if target == 0 {
			//已找到组合,go二维数组append
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		
		// 直接跳过
		dfs(target, idx+1)
		
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	
	dfs(target, 0)
	return
}

  一个dfs里面调用2个dfs函数,这样的递归形成了一个类似树的结构,这个递归注意终止条件,每个数可以选也可以不选,因为数组里面的元素可以重复使用。力扣上的图很详细的表现了过程。

面试腾讯算法:组合总和

 

说明:图片和代码均来自于力扣

参考地址:https://leetcode-cn.com/problems/combination-sum/solution/zu-he-zong-he-by-leetcode-solution/

上一篇:【回溯算法】四、回溯模板


下一篇:Leetcode 组合总和 与 排列组合相关问题