40组合总和II
题目:给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
来源:https://leetcode-cn.com/problems/combination-sum-ii/
法一:自己的代码
思路:与39组合总和最大的区别是每次回溯时遍历的数组不一样,39中由于数字可以重复使用,所以每次遍历的时候,总是从该数字开始,而40不一样,不可重复所以要加1,从下一个数字开始遍历.
class Solution: def combinationSum(self, candidates, target: int): candidates = sorted(candidates) print(candidates) results = [] def backtrack(a=[], candidates=candidates): if sum(a) == target: results.append(a) return for j,i in enumerate(candidates): # 使用这个前提是要排序 # 画一个树状图便很容易看出,如果连续出现了两个相同的数, # 第二个数再遍历有可能会和第一个数的遍历结果重复 if (j != 0) & (candidates[j] == candidates[j - 1]): continue if sum(a) + i <= target: # 这里candidates[j+1:]是关键,根本原因是因为题中要求所给数组中的每个数字只可以使用一次 # 每次遍历的时候务必只遍历[j+1,)中的数,这样才能保证每个数字只使用一次,类似一往无前法, # 如果j已经到达最大的索引了,说明这轮已经遍历完了, # 传过去的是一个空的list,即下次遍历一个空list也不影响程序 backtrack(a + [i], candidates[j+1:]) # 如果大于了,后面的数也就不用遍历了,因为前面的数小后面的大,小的不行大的一定不行 else: break backtrack() return results if __name__ == "__main__": duixiang = Solution() # a = duixiang.combinationSum([1,1,2],4) # print('u',a) a = duixiang.combinationSum([2,5,3,1,2],5) print('u',a)