其他
一道 LeetCode 题带我们深入二进制表示、搜索策略和剪枝
(给算法爱好者加星标,修炼编程内功)
来源:TechFlow-梁唐
描述
所有的元素都是正数 所有元素没有重复 答案不能有重复 每一个元素可以使用若干次
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题解
二进制表示法
回到问题
搜索解决一切
def dfs(x, sequence, candidates target):
if x == target:
ans.append(sequence)
return
for i in candidates:
if x + i > target:
continue
sequence.append(i)
dfs(x+i, sequence, candidates, target)
sequence.pop()
class Solution:
def dfs(self, ret, pos, sequence, now, target, candidates):
if now == target:
# 加入答案,需要.copy()一下
ret.append(sequence.copy())
return
for i in range(pos, len(candidates)):
# 如果过大则不递归
if now + candidates[i] > target:
continue
# 存入sequence,往下递归
sequence.append(candidates[i])
self.dfs(ret, i, sequence, now+candidates[i], target, candidates)
sequence.pop()
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret = []
self.dfs(ret, 0, [], 0, target, candidates)
return ret
题目变形
idx: pos pos+1 pos+2 pos+3(i)
candidates: 1 2 2 2
idx: pos pos+1 pos+2 pos+3(i)
candidates: 2 2 2 2
class Solution:
def dfs(self, ret, sequence, now, pos, target, candidates):
if now == target:
ret.append(sequence.copy())
return
for i in range(pos+1, len(candidates)):
cur = now + candidates[i]
# 剪枝
# 如果多个相同的元素,必须保证先去最前面的
if cur > target or (i > pos+1 and candidates[i] == candidates[i-1]):
continue
sequence.append(candidates[i])
self.dfs(ret, sequence, cur, i, target, candidates)
sequence.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 排序,保证相同的元素放在一起
candidates = sorted(candidates)
ret = []
self.dfs(ret, [], 0, -1, target, candidates)
return ret
觉得本文有帮助?请分享给更多人
关注「算法爱好者」加星标,修炼编程内功
好文章,我在看❤️