专栏首页前端小书童一天一大 lee(组合总和 II)难度:中等-Day20200910

一天一大 lee(组合总和 II)难度:中等-Day20200910

题目:

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例:

  1. 示例 1
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  1. 示例 2
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

抛砖引玉

抛砖引玉

思路

本题逻辑的重点在不允许 candidates 的元素重复使用,但是 candidates 元素本身可能存在重复元素

  • candidates 中同一个元素不能在一种组合中重复使用
  • 结果元素相同组成的子元素位置不同算作一种结果

day-08: 组合 (难度:中等)

day-09: 组合总和 (难度:中等)

在前两天的题目中分别用:

  1. 指针驱动选择生成组合
  2. 指针约束区域枚举指定区域元素来枚举组合

两种形式处理了递归回溯子元素组合的问题

结合本题的要求:

  • 指针可以协助完成同一个元素不能在一种组合中重复使用
  • 如果采用指针驱动的形式,发现很难避免不同位置的元素形成相同元素的结果,而采用约束区域来枚举元素的形状,相同的元素(对 candidates 排序,相邻元素相同)被指针约束则很好避免在不同个组合中信息相同个元素

实现

  • 对 candidates 排序(将相同元素排列在一起,方便指针控制元素不重复参与组合)
  • 递归,从i之后遍历为参与组合元素:
  • 在i指针之后遇到相同元素,则不再选择i处元素,因为此时已回溯,再次选择i处元素则形成了重复的组合
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  let _result = []
  candidates = candidates.sort((a, b) => a - b)
  function dfs(i, item, sum) {
    if (sum === target) {
      _result.push(item)
      return
    }
    for (let x = i; x < candidates.length; x++) {
      if (target - sum - candidates[x] >= 0) {
        // i指针所在元素如果后面还有与其相同的元素,则不再选择i处元素,因为此时已回溯,再次选择i处元素则形成了重复的组合
        if (x != i && candidates[x] == candidates[x - 1]) continue
        item.push(candidates[x])
        dfs(x + 1, [...item], sum + candidates[x])
        item.pop()
      }
    }
  }
  dfs(0, [], 0)
  return _result
}

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 lee(组合总和)难度:中等-Day20200909

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

    前端小书童
  • 【一天一大 lee】去除重复字母 (难度:中等) - Day20201220

    s 中元素逐个入栈,如果遇到 Unicode 较小的元素,尽量将其放大栈底部 (如果后续还有栈内已经排列的原则,则出栈让 Unicode 较小的元素先入栈)

    前端小书童
  • 一天一大 lee(回文对)难度:困难-Day20200806

    给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

    前端小书童
  • UC Berkeley EECS系是如何培养计算机学生的

    加州大学伯克利分校电子工程和计算机科学系(EECS)是世界知名的院系,计算机领域在2020 USNews排名第一[1]。EECS的使命是教育、创新和服务社会。自...

    陆道峰
  • Python序列元素计数的方法,你知道几种?

    在Python脚本语言中,数据结构有许多种,常见的数据类型有:序列,映射与集合三大类型,其中序列又分为可变序列和不可变序列,可变序列有2类:列表(List)与字...

    企鹅号小编
  • 【深度干货】专知主题链路知识推荐#9-机器学习中的变分推断方法(Variational Inference)简介02

    【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工智能( 机器学习、自然语言处理、计算机视...

    WZEARW
  • YoyoGo基于ASP.NET Core设计的Golang实现

    YoyoGo 是一个用 Go 编写的简单,轻便,快速的 微服务框架,目前已实现了Web框架的能力,但是底层设计已支持多种服务架构。

    yoyofx
  • 泛微 e-cology OA 远程代码执行漏洞复现

    Poc已在github公开,由于环境搭建较为复杂,所以我在空间搜索引擎中找了国外的网站进行复现

    用户1631416
  • LDA详解:自然语言处理

          LDA,其实有两种含义,一种是统计学中的分析方法:线性判别分析(Linear Discriminant Analysis),一种概率主题模型:隐含...

    学到老
  • 腾讯安全月报 | AI安全最新成果、物联网安全标准立项、云安全威胁报告发布……

    腾讯安全

扫码关注云+社区

领取腾讯云代金券