https://leetcode-cn.com/problems/combination-sum-ii/
# -*- coding:utf-8 -*- class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ candidates.sort() n = len(candidates) res = [] def backtrack(i, tmp_sum, tmp): """ 回溯法 :param i: 当前选择的索引 :param tmp_sum: 当前已选择所有数的和 :param tmp: 当前已选择数的列表 :return: """ if tmp_sum > target or i == n + 1: return if tmp_sum == target: res.append(tmp) return for j in range(i, n): if tmp_sum + candidates[j] > target: break backtrack(j + 1, tmp_sum + candidates[j], tmp + [candidates[j]]) backtrack(0, 0, []) res_final = [] # 去重 for each in res: if each not in res_final: res_final.append(each) return res_final if __name__ == '__main__': # candidates = [10, 1, 2, 7, 6, 1, 5] # target = 8 candidates = [2, 5, 2, 1, 2] target = 5 print(Solution().combinationSum(candidates, target))
思路:这道题和上一道题十分类似,不同的就是需要做一些处理。
比如上一道题允许一个数字使用多次,因此递归调用的时候依然传入j,但是这道题不允许重复使用,因此下一次查找应该是j+1次。
上一道题题中写到没有重复元素,这一道题允许重复元素,因此在返回前要做一次去重。
上一道题边界条件是i==n,理由和第一条差不多,因为是传入j,而这道题是j+1,因此边界条件也应该变成n+1。
0 条评论