首先回顾一下39题，这次用Python写。39题区别就是可以重复访问同一位置的元素。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, start, nums, path, res, target):
if target == 0:
res.append(path)
return
for i in range(start, nums):
if target - candidates[i] < 0: break
dfs(candidates, i, nums, path + [candidates[i]], res, target - candidates[i])
res = []
path = []
nums = len(candidates)
candidates.sort()
dfs(candidates, 0, nums, path, res, target)
return res
|
为了避免访问同一位置的元素，排序过后的数组由于相同元素都是紧挨着的，只要排除前一个数字和当前相等的情况就好了，也就是candidates[i] != candidates[i-1]。但是如果此时i是迭代起点，则这一条件也过滤掉了当前迭代，这是不应该发生的。因此需要加以判断：i > start。根据上面39的代码微调后解答如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, start, nums, path, res, target):
if target == 0:
res.append(path)
return
for i in range(start, nums):
if target - candidates[i] < 0: break
if i > start and candidates[i] == candidates[i-1]: continue
dfs(candidates, i+1, nums, path + [candidates[i]], res, target - candidates[i])
res = []
path = []
nums = len(candidates)
candidates.sort()
dfs(candidates, 0, nums, path, res, target)
return res
|
