2023-12-25 组合总和和组合总和 II

2024-01-02 22:39:05

39. 组合总和

在这里插入图片描述

思路：把它抽象成为回溯树！使用回溯三部曲！重点就获取到的集合需要进行去重操作！

39.组合总和

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.backtrack(candidates, target, [], result, 0)
        return result
    # 传入参数
    def backtrack(self, candidates, target,  temp_list, result, cur):
        # 结束条件
        if target == cur:
            # 去重元素
            temp = sorted(temp_list)
            if temp not in result:
                result.append(temp) 
        elif cur > target:	# 进行剪枝
            return
        for i in candidates:
            cur += i
            temp_list.append(i)
            self.backtrack(candidates, target, temp_list, result, cur)
            cur -= i
            temp_list.pop()

40. 组合总和 II

在这里插入图片描述

思想：就是上面这题的演变了！都不需要改动什么代码！只需要加一个判断进行取出大量的重复元素即可！

img

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.backtrack(candidates, target, 0, [], 0, result)
        return result
    # 传入参数
    def backtrack(self, candidates, target, index, temp_list, cur, result):
        # 结束条件
        if cur == target:
            if temp_list not in result:
                result.append(temp_list[:])
        elif cur > target:
            return 
        for i in range(index, len(candidates)):
            # 去重全是一样的数据
            if i  > index and candidates[i] == candidates[i - 1]:
                continue
            cur += candidates[i]
            temp_list.append(candidates[i])
            self.backtrack(candidates, target, i + 1,temp_list, cur, result)
            cur -= candidates[i]
            temp_list.pop()

文章来源:https://blog.csdn.net/niuzai_/article/details/135350499
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。