回溯法

发表于 | 分类于

39.数组总和

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

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

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

可以使用回溯算法进行解题，其实回溯比较公式化，写题时有种套公式的感觉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
	def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
		tmp = []
		ret = []
		def backtrack(x):
			if x == 0:
				# 这里需要使用拷贝，不然结果会错误
				t = tmp.copy()
				# 因为没有剪枝，所以需要去重
				t.sort()
				if t not in ret:
					ret.append(t)
				return
			if x< 0:
				return
			for i in candidates:
				tmp.append(i)
				x -= i
				backtrack(x)
				x += i
				tmp.pop(-1)
		backtrack(target)
		return ret