组合+回溯

一、39. 组合总和 1.1、题目描述

1.2.1、排序+回溯+剪枝

class Solution:
    def __init__(self) -> None:
        self.res = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 预排序
        candidates.sort()
        self.__dfs(target, [], candidates)
        return self.res
    
    def __dfs(self, target: int, tmpList: List[int], tmpCandidates: List[int]) -> None:
        if target == 0:
            self.res.append(tmpList)

        if target  target:
                break
            self.__dfs(target-tmpCandidates[i], tmpList + [tmpCandidates[i]], tmpCandidates[i:])

二、40. 组合总和 II 2.1、题目描述 2.2.1、排序+去重+回归

class Solution:
    def __init__(self) -> None:
        self.res = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 预排序
        candidates.sort()
        self.__dfs(target, [], candidates, 0)
        return self.res
    
    def __dfs(self, target: int, tmpList: List[int], tmpCandidates: List[int], idx: int) -> None:
        if target == 0:
            self.res.append(tmpList)
            return 

        if target  target:
                break
            # 去重  和 1.2.1区别
            if i > idx and tmpCandidates[i] == tmpCandidates[i-1]:
                continue

            self.__dfs(target-tmpCandidates[i], tmpList + [tmpCandidates[i]], tmpCandidates, i+1) # 注意此处i+1

三、216. 组合总和 III 2.1、题目描述 2.2.1、相当于39. 组合总和的变种

class Solution:
    def __init__(self) -> None:
        self.res = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.__dfs(n, [], 1, k)
        return self.res
    
    def __dfs(self, target: int, tmpList: List[int], left: int, k: int) -> None:
        if target == 0 and len(tmpList) == k:
            self.res.append(tmpList)
            return 

        if target  target:
                break
            self.__dfs(target-i, tmpList + [i], i+1, k)

四、377. 组合总和 Ⅳ 五、77. 组合 5.1、题目描述

5.2.1、相当于39. 组合总和的变种

class Solution:
    def __init__(self) -> None:
        self.res = []

    def combine(self, k: int, n: int) -> List[List[int]]:
        self.__dfs([], 1, n, k+1)
        return self.res
    
    def __dfs(self, tmpList: List[int], left: int, k: int, n: int) -> None:
        if len(tmpList) == k:
            self.res.append(tmpList)

        for i in range(left, n):
            if len(tmpList) >= k:
                break
            self.__dfs(tmpList + [i], i+1, k, n)