【刷题DAY24】77.md

发表于 | 分类于

77. 组合

题目链接：https://leetcode.cn/problems/combinations/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 回溯
    • 回溯必有递归
    • 回溯法其实就是暴力查找，并不是什么高效的算法。
    • 解决几类问题，可以看出每一类问题都不简单
      • 组合问题：N个数里面按一定规则找出k个数的集合
      • 切割问题：一个字符串按一定规则有几种切割方式
      • 子集问题：一个N个数的集合里有多少符合条件的子集
      • 排列问题：N个数按一定规则全排列，有几种排列方式
      • 棋盘问题：N皇后，解数独等等
    • 回溯可看成树形结构（N叉树），并给出了回溯法的模板。
    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void backtracking(参数) {
          if (终止条件) {
              存放结果;
              return;
          }

          for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
              处理节点;
              backtracking(路径，选择列表); // 递归
              回溯，撤销处理结果
          }
      }
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      class Solution:
          def combine(self, n: int, k: int) -> List[List[int]]:
              path = []
              result = []

              def backtrack(n, k, startIdx):
                  if(len(path) == k):
                      result.append(path[:])
                      return 

                  for i in range(startIdx, n - (k - len(path)) + 2): # 剪枝优化在这里
                      path.append(i)
                      backtrack(n, k, i+1)
                      path.pop()
              backtrack(n, k, 1)
              return result

      0x5 今日收获，记录一下自己的学习时长

  • 1.5h

待重点复习

77

总结

  • 回溯