leetcode 39 组合总和
通过回溯,以及按大小剪枝,因为组合问题所以需要固定一个顺序遍历,因为不同顺序也被视为一个组合。保证path数组中的顺序是升序的。
遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要按某种顺序搜索。
注意:这里的顺序不仅仅指数组 candidates 有序,还指按照一定顺序搜索结果。
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(path,result,target): if target==0: result.append(path[:]) return if target<0: return for j in range(len(candidates)): if len(path)!=0 and path[-1]>candidates[j]:continue path.append(candidates[j]) dfs(path,result,target-candidates[j]) path.pop() result=[] dfs([],result,target) return result
Python3 的 [1, 2] + [3] 语法生成了新的列表,一层一层传到根结点以后,直接 res.append(path) 就可以了;
基本类型变量在传参的时候,是复制,因此变量值的变化在参数里体现就行,所以 Python3 的代码看起来没有「回溯」这个步骤。
有些朋友可能会疑惑什么时候使用 used 数组,什么时候使用 begin 变量。这里为大家简单总结一下:
排列问题,讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时),需要记录哪些数字已经使用过,此时用 used 数组;
组合问题,不讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时),需要按照某种顺序搜索,此时使用 begin 变量。
作者:liweiwei1419
链接:https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
每次从当前搜索的起点出发,注意因为可以重复从当前节点出发,如果不能重复那么从当前加1的位置出发。
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(i,path,result,target): if target==0: result.append(path[:]) return #if target<0: #return for j in range(i,len(candidates)): if target-candidates[j]<0:continue path.append(candidates[j]) dfs(j,path,result,target-candidates[j]) path.pop() if len(candidates)==0: return [] result=[] dfs(0,[],result,target) return result