组合型回溯＋剪枝

本篇基于b站灵茶山艾府。

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 与子集型组合唯一的区别在于path数组长度是确定的
        # dfs(i)表示在下标小于等于i的数组中选择k个数的组合
        # 1.选或不选
        # def dfs(i):
        #     nonlocal k
        #     if k == 0:	# 已经选完了k个数，不用再继续递归
        #         ans.append(path.copy())
        #         return
        #     if i == 0:
        #         return
        #     dfs(i - 1)
        #     k -= 1
        #     path.append(i)
        #     dfs(i - 1)
        #     path.pop()
        #     k += 1
        # 2.枚举选哪个数
        def dfs(i):
            nonlocal k
            if k == 0:
                ans.append(path.copy())
            for j in range(i, 0, -1):
                k -= 1
                path.append(j)
                dfs(j - 1)
                path.pop()
                k += 1
        path = []
        ans = []
        dfs(n)
        return ans

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

  返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

  示例 1:

  输入: k = 3, n = 7
  输出: [[1,2,4]]
  解释:
  1 + 2 + 4 = 7
  没有其他符合的组合了。
  

  示例 2:

  输入: k = 3, n = 9
  输出: [[1,2,6], [1,3,5], [2,3,4]]
  解释:
  1 + 2 + 6 = 9
  1 + 3 + 5 = 9
  2 + 3 + 4 = 9
  没有其他符合的组合了。
  

  示例 3:

  输入: k = 4, n = 1
  输出: []
  解释: 不存在有效的组合。
  在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
  

  ---

  class Solution:
      def combinationSum3(self, k: int, n: int) -> List[List[int]]:
          # dfs(i)表示从[1,i]中选择相加之和为n的k个数的集合
          # 1.选/不选
          # def dfs(i):
          #     nonlocal k, n
          #     # 剪枝，如果最大的k个数不能构成n，那么后面怎么递归都无法得出答案
          #     if i >= k and n > (i + i - k + 1) * k // 2:
          #         return
          #     if k == 0 and n == 0:
          #         ans.append(path.copy())
          #         return
          #     if i == 0:
          #         return
          #     dfs(i - 1)  # 不选当前数字
          #     k -= 1
          #     n -= i
          #     path.append(i)
          #     dfs(i - 1)
          #     path.pop()
          #     n += i
          #     k += 1
          # 2.枚举选哪个数字
          def dfs(i):
              nonlocal k, n
              if i >= k and n > (i + i - k + 1) * k // 2:
                  return
              if n == 0 and k == 0:
                  ans.append(path.copy())
                  return
              for j in range(i, 0, -1):
                  k -= 1
                  n -= j
                  path.append(j)
                  dfs(j - 1)
                  n += j
                  k += 1
                  path.pop()
          path = []
          ans = []
          dfs(9)
          return ans
  

  ---

  22. 括号生成

  数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  示例 1：

  输入：n = 3
  输出：["((()))","(()())","(())()","()(())","()()()"]
  

  示例 2：

  输入：n = 1
  输出：["()"]
  

  ---

  class Solution:
      def generateParenthesis(self, n: int) -> List[str]:
          # def(i)表示在下标大于等于i的位置中生成所有可能的有效括号组合
          # 什么时候可以放左括号？
          # 只要左括号个数小于n，都可以放
          # 什么时候可以放右括号？
          # 已经放的右括号个数小于左括号个数时，就可以放
          def dfs(i):
              nonlocal left, right
              if i == n * 2:
                  ans.append("".join(path))
              if left  
  
  （图片来源网络，侵删）
  （图片来源网络，侵删）
  （图片来源网络，侵删）