代码随想录算法训练营第二十天 | leetcode:回溯算法理论基础,组合问题

前段时间有事,落下了不少二叉树章节。所以跳级更新回溯算法,后续抽空再补上落下的章节。:tired_face::tired_face::tired_face::tired_face:

回溯算法理论基础

  • 回溯法也可以叫做回溯搜索法,它是一种搜索的方式。回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案。与暴力for循环没啥本质区别,只是使用递归省略了多层嵌套的情况。所以可以大概的理解为,回溯算法是for+递归。回溯法解决的问题可以抽象为树形结构for遍历第一层横向,递归遍历纵向。想象遍历多个二叉树,应该比较好理解。

代码随想录算法训练营第二十天 | leetcode:回溯算法理论基础,组合问题

  • 回溯法,一般可以解决如下几种问题:

    • 组合问题:N个数里面按一定规则找出k个数的集合
    • 切割问题:一个字符串按一定规则有几种切割方式
    • 子集问题:一个N个数的集合里有多少符合条件的子集
    • 排列问题:N个数按一定规则全排列,有几种排列方式
    • 棋盘问题:N皇后,解数独等等
  • 附上卡哥总结的回溯模板,嘎嘎好用:smirk:

    void backtracking(参数) {
      if (终止条件) {
          存放结果;
          return;
      }
    
      for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
          处理节点;
          backtracking(路径,选择列表); // 递归
          回溯,撤销处理结果
      }
    }

    Problem: 77. 组合

    注意的地方

    回溯算法可以进行剪枝操作进行优化,即:当剩余元素比组合数k小时可以跳出for循环。举一个例子,n = 4,k = 4的话,那么第一层for循环的时候,从元素2开始的遍历都没有意义了。 在第二层for循环,从元素3开始的遍历都没有意义了。

代码随想录算法训练营第二十天 | leetcode:回溯算法理论基础,组合问题

code

class Solution {

    private $res = [];//二位数组结果集
    private $path = [];//单次结果集
    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer[][]
     */
    function combine($n, $k) {
        $this->backtracking($n, $k, 1);
        return $this->res;
    }

    function backtracking($n, $k, $startIndex){
        //判断当前组合是否等于k组合数长度
        if(count($this->path) == $k){
            //把path结果存入目标数组
            $this->res[] = $this->path;
            return;
        }
        //对进行外层循环 循环n次 
        $pathLen = count($this->path);
        //还需要的元素个数为: k - $pathLen; 总共还剩下多少个元素:$n-($k-$pathLen); 因为包括起始位置所以需要+1
        for($i = $startIndex; $i <= $n-($k-$pathLen)+1; $i++){
            //把组合元素放进数组
            $this->path[] = $i;
            //下一次循环从下一个数开始,所以$startIndex = $i+1
            $this->backtracking($n, $k, $i+1);
            //当i=4时,触发一次递归的回溯,一次for循环结束的回溯
            array_pop($this->path);
        }
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!