9feedb6305a5bb4f0246e9e4c5df3b64
(难度Medium)Problem 39. Combination Sum(拆分数字)

链接

https://leetcode.com/problems/combination-sum/

难度等级

Medium

题干

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.

题意

给定一个数组和一个数字target,求出使用数组当中的元素组合成target的所有可能。

有几点需要注意

  1. 候选集当中不会出现重复的元素
  2. 同一个的元素可以选择多次
  3. 答案当中不能出现相同的组合

意思是说[2, 2, 3]和[3, 2, 2]是一样的

样例

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题解

解法一 暴力

既然是寻找所有可能解,那么自然可以用暴力的方法。但是由于同一个元素可以使用多次,我们并不能直接排列组合候选集。这个问题也很好解决,我们用多个重复元素代替一个就行了。

比如说target是7,候选集是[2, 3, 5]。由于3个2相加小于7,4个2相加大于7.同理,3最多取2个,5最多只能取1个。我们可以把候选集变成[2, 2, 2, 3 ,3 ,5]。对这个新的候选集计算排列组合,寻找答案再进行查重过滤即可。

排列组合的方法有很多,比较简单的是调用系统函数,比如next_permutation。

或者可以使用递归的方法来构造,不过既然都会递归了,为什么还要用这种方法呢?

所以暴力求解只是一个理论上可行的方法,有能力写出来的同学,基本上也一定能写出更好的方法。于是我就不写伪代码添乱了。

解法二 回溯

如果之前能把数独那道题做出来,那么这道题想必更不在话下了。本质上其实也是一个回溯的搜索问题。

而且比数独那题要简单得多。

top Created with Sketch.