dfs的两种不同架构
第一种
def dfs(u):
res.append(pt[:])
if u == len(nums):
return None
for i in range(len(nums)):
pt.append(nums[i])
dfs(u + 1)
pt.pop()
res = []
pt = []
nums = list(map(int, input().split()))
dfs(0)
print(res)
# 结果
1 2 3
[[], [1], [1, 1], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 3], [1, 3, 1], [1, 3, 2], [1, 3, 3], [2], [2, 1], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 2], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3], [3], [3, 1], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 2], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 3], [3, 3, 1], [3, 3, 2], [3, 3, 3]]
第二种
def dfs(u):
res.append(pt[:])
if u == len(nums):
return None
for i in range(u, len(nums)):
pt.append(nums[i])
dfs(i + 1)
pt.pop()
res = []
pt = []
nums = list(map(int, input().split()))
dfs(0)
print(res)
# 结果
1 2 3
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
这样我们可以根据第二种思路,对其进行简单的修改,代码如下:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort() # 先排序,方便处理重复元素
res = []
pt = []
def dfs(start, cur_target):
if cur_target == 0:
res.append(pt[:])
return
if cur_target < 0:
return
for i in range(start, len(candidates)):
# 这里要注意,i != start,这样可以保证:如果列表为[1, 1, 1, .....],那么我选择前面两个1和选择第一个和第三个或者选择后面两个1是相同的
if i > start and candidates[i] == candidates[i - 1]:
continue # 跳过重复的元素
if candidates[i] > cur_target:
break # 因为已排序,后面的数字都会更大,可以直接跳出循环
pt.append(candidates[i])
dfs(i + 1, cur_target - candidates[i])
pt.pop()
dfs(0, target)
return res