面试腾讯算法：组合总和

本文主要是介绍面试腾讯算法：组合总和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

      给定一个无重复元素的数组 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/

这篇关于面试腾讯算法：组合总和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！