my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

LeetCode(5)-回溯与剪枝

王伟2020年9月9日54人围观
简介LeetCode(5)-回溯与剪枝

LeetCode(5)-回溯与剪枝

LeetCode每日一题连续两天都是回溯与剪枝

回溯:在包含问题的所有的解的空间树中,按DFS的方法,从根节点出发,搜索整棵解空间树。

回溯的要点是把状态还原成进入当前节点时的状态

剪枝就是为了避免无效的搜索

组合

给定两个整数 n  k返回 1 ... n 中所有可能的 k 个数的组合

示例:

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

借用一个LeetCode大佬的图解

const combine = (n, k) => {
  const res = [];

  const helper = (start, path) => { 
    if (path.length == k) {
      res.push(path.slice());       // 推入res
      return;                       // 结束当前递归
    }
    for (let i = start; i <= n; i++) { 
      path.push(i);                    // 传入到字数组中
      helper(i + 1, path);             // 不重复的数字组合 传入i+1
      path.pop();                      // 撤销选择
    }
  };

  helper(1, []);
  return res;
}

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合

candidates 中的数字可以无限制重复被选取

说明

所有数字包括 target都是正整数
解集不能包含重复的组合 
示例 1

输入candidates = [2,3,6,7], target = 7,
所求解集为
[
  [7],
  [2,2,3]
]
示例 2

输入candidates = [2,3,5], target = 8,
所求解集为
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题意:给你一个数组,里面都是不带重复的正数,还给你一个 target,求出所有和为 target 的组合。元素可以重复使用,但组合不能重复。

可以对比第一题很好理解

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const res = []
    let num = 0 
    const helper = function(start,path){
        if(num>=target){
                if(num == target){
                    res.push(path.slice())
                }
                return
            }
        for(let i = start;i<candidates.length;i++){
            num += candidates[i] //用于判断组合num是否和target相等
            path.push(candidates[i]) // 加入到字数组中
            helper(i,path) // 由于可以重复使用 这里传入的是i 而非i+1
            num -= candidates[i] // 撤销回退
            path.pop() // 字数组撤销回退
        }
    }
    helper(0,[])
    return res
};

连续几天的回溯与剪枝,和LeetCode大佬学习收获还是很大的!

路漫漫其修远兮,吾将上下而求索!


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话