39. Combination Sum

给定一组数字和一个目标数字，找到所有能加起来和是目标数字的组合，每个数字可以不限次数的使用

思路： dfs, 先排序，以及如果当前组合的和大于目标值则后面的就不用继续了，可以省点时间

Python：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
   def combinationSum(self, candidates, target):
       """
       :type candidates: List[int]
       :type target: int
       :rtype: List[List[int]]
       """
       # 5 star, 
       rs = []
       candidates.sort()
       self.dfs(0, candidates, [], rs, target)
       return rs

   def dfs(self, current_sum, candidates, path, rs, target):
       if current_sum == target:
           rs.append(path)
       elif current_sum > target:
           return
       else:
           for i in range(len(candidates)):
               if current_sum+candidates[i] > target:
                   break
               self.dfs(current_sum+candidates[i], candidates[i:], path+[candidates[i]], rs, target)

Go:

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
26
27
28
29
30
31
func combinationSum(candidates []int, target int) [][]int {
	var ret [][]int
	retP := &ret
	sort.Ints(candidates)
	dfs(candidates, target, []int{}, 0, retP)
	return *retP
}


func dfs(candidates []int, target int, path []int, curSum int, retP *[][]int) {
	//fmt.Println(path, curSum)
	if curSum == target {
		tempPath := make([]int, len(path))
		copy(tempPath, path)
		*retP = append(*retP, tempPath)  // 注意这里，是将path拷贝到一个新的切片，然后加到结果retP中，
		// 如果直接加，会出现问题，会发现原来加进去的切片的值被修改，不是我们想要的切片值，
		// 估计是由于切片都是基于一个数组，后面对切片的修改修改了底层的数组，所以前面切片的取值也会变化
		return
	}
	for index, val := range candidates {
		if curSum + val <= target {
			// 这里又是奇怪的一处，path和curSum如果按下面注释的那样先计算，再调用，结果又不对, 会少了几个结果集，
			// 猜测是计算后的赋值影响了后来的调用，还不太清楚
			//curSum += val
			//path = append(path, val)
			//dfs(candidates[index:], target, path, curSum, retP)
			dfs(candidates[index:], target, append(path, val), curSum+val, retP)

		} else {break}
	}
}