40. Combination Sum II

给定一个包含一些数字的列表和一个目标值，在这个列表中所有结果的和是目标值的组合

思路： 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
24
25
26
class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 5 star, dfs，需要注意去重
        candidates.sort()
        rs = []
        self.dfs(0, candidates, [], rs, target)
        return rs

    def dfs(self, current_sum, candidates, path, rs, target):
        if current_sum == target:
            rs.append(path)
            return
        elif current_sum > target:
            return
        else:
            for i in range(len(candidates)):
                if i > 0 and candidates[i] == candidates[i-1]:
                    continue
                if current_sum + candidates[i] > target:
                    break
                self.dfs(current_sum+candidates[i], candidates[i+1:], 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
func combinationSum2(candidates []int, target int) [][]int {
	var ret [][]int
	retP := &ret
	sort.Ints(candidates)
	dfs(candidates, target, 0, []int{}, retP)
	return *retP

}

func dfs(candidates []int, target int, curSum int, path []int, retP *[][]int) {
	if curSum == target {
		tempPath := make([]int, len(path))  //创建了切片的拷贝，避免后续的修改影响已加入结果集的切片的取值
		copy(tempPath, path)
		*retP = append(*retP, tempPath)
		return
	}
	for index, val := range candidates {
		if index == 0 || candidates[index] > candidates[index-1] { //避免重复
			if curSum + val > target {
				return
			} else {
				dfs(candidates[index+1:], target, curSum+val, append(path, val), retP)
			}

		}

	}
}