题目描述 Given a set of candidate numbers ( candidates ) ( without duplicates ) and a target number ( target ), find all unique combinations in candidates where the candidate numbers sums to target . The same repeated number m" />
  • 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0704/5319.html 1190000019658369nd">

题目描述

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

大意:给定一组不含重复数字的数组和一个目标数字,在数组中找出所有数加起来等于给定的目标数字的组合。

输入

candidates = [2,3,6,7], target = 7

输出

[
  [7],
  [2,2,3]
]

分析题目

由于我们需要找到多个组合,简单的使用 for 循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。

用回溯算法解决问题的一般步骤:

  1. 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。
  2. 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
  3. 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

根据题目的描述我们知道它满足了我们所说的步骤一,下面我们来确定搜索的思路

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!