【Python】回溯之组合问题

求组合问题，回溯+剪枝，非常优秀

40. 组合总和 II

https://leetcode.cn/problems/combination-sum-ii/

思路：

• 求不重复的的全排列，首先确定用回溯+剪枝
• 递归结束条件：
  • 当rest剩余值 < 0时，return
  • 当rest == 0时，把该排列加入ans中
• 递归体：
  • 如果求全排列（不要求重复），先不考虑剪枝情况，每个数只取一遍，从startIndex开始，直接path.append(当前值)
  • 递归函数，rest = rest - candidates[i]， startIndex = i+1
  • 回溯，将之前的路pop掉
• 考虑剪枝（要求不重复）
  • candidates.sort()，非常重要，便于剪枝
  • 此时，为了得到不重复的排列，每层append一个值，必须保证每层append的值不一样，需要进行判断，跳过该枝丫

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        ans = []
        # path中的元素可以相同，但是path整体不应该相同
        # 剪枝策略：同一个节点产生的分支，边上减去的数相同的分支，只保留第一个，即每一层，保证path.append()的值都不相同
        def backtracking(candidates, rest, path, startIndex):
            if rest < 0:
                return
            if rest == 0:
                ans.append(path[:])
                return
            for i in range(startIndex, n):
                if i > startIndex and candidates[i] == candidates[i-1]: continue
                path.append(candidates[i])
                backtracking(candidates, rest - candidates[i], path, i+1)
                path.pop()

        backtracking(candidates, target, [], 0)
        return ans

216. 组合总和 III

https://leetcode.cn/problems/combination-sum-iii/

思路：同上

PS：为什么组合②比组合③简单？！

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        def backtracking(path, rest, startNum):
            if rest < 0 or len(path) > k:
                return 
            if rest == 0 and len(path) == k:
                ans.append(path[:])
                return
            for cur_num in range(startNum, 10):
                path.append(cur_num)
                backtracking(path, rest-cur_num, cur_num+1)
                path.pop()
        backtracking([], n, 1)
        return ans

PS：这两天在面试华为od，忘记更新了，看看情况出个华为od面经，想要了解od的可以私信我