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.
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]
]
组合数的和 1
这题就是 给定一个 去重的数组 candidate , 比如[2,3,6,7],和一个 target， 比如8,返回 candidate 中所有 数字和 等于 target 的组合。
比如[2,2,3] 就等于 target.
这里有几个注意点
- 他这个题， 组合数选取 是有放回的， 简单说就是 每个数可以重复选择无数次。
-
candidate不一定是有序的 - solution 在元素层面上不允许重复， 比如
candidate=[2,3,4]，[2,2,3]和[2,3,2]是相同的, 就是 你选完当前的数， 你只能选从当前的数往后选， 不能往前选。 -
candidate和target都是正整数
我这里写了个递归的方法。
class Solution:
def __init__(self):
self.ans = []
self.candidates = []
self.target = 0
def _combinationSum(self,cur,l):
if sum(l) > self.target or cur > len(self.candidates)-1 :
return
if sum(l) == self.target:
self.ans.append(l)
return
# 递归
for e in range(cur,len(self.candidates)):
self._combinationSum(e,l+ [self.candidates[e]])
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.candidates = candidates
self.target = target
for i in range(len(candidates)):
self._combinationSum(i,[self.candidates[i]])
return self.ans
可以发现，递归所有情况速度会很慢，
如果这个 candidate 是增序的，我们就可以优化剪枝。
class Solution:
def __init__(self):
self.ans = []
self.candidates = []
self.target = 0
def _combinationSum(self,cur,l):
if cur > len(self.candidates)-1 :
return
if sum(l) == self.target:
self.ans.append(l)
return
# 递归
for e in range(cur,len(self.candidates)):
if sum(l + [self.candidates[e]]) > self.target:
break;
self._combinationSum(e,l+ [self.candidates[e]])
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.candidates = sorted(candidates)
self.target = target
for i in range(len(candidates)):
if self.candidates[i] > self.target:
break;
self._combinationSum(i,[self.candidates[i]])
return self.ans
组合数的和 2
leetcode 40
这题就是把上题的 有放回 改成 无放回。
比如[2,3]， target = 4, 这是就不存在[2,2],这种解了，每个元素只能使用一次。
另外这题还要求不能出现重复解。
所以这题在上题的基础上 改动2个地方
self._combinationSum(i,[self.candidates[i]])
self._combinationSum(e,l+ [self.candidates[e]])
# 无放回
self._combinationSum(i+1,[self.candidates[i]])
self._combinationSum(e+1,l+ [self.candidates[e]])
# 有放回
- 去重
比如[1,2,2,3]在递归过程中， 第二个2应该被直接跳过。
# 去重
if i> 0 and self.candidates[i] == self.candidates[i-1]:
continue
if e > cur and self.candidates[e] == self.candidates[e-1]:
continue
所以这题在上题基础上简单修改下就好了。
class Solution:
def __init__(self):
self.ans = []
self.candidates = []
self.target = 0
def _combinationSum(self,cur,l):
if sum(l) == self.target:
self.ans.append(l)
return
if cur > len(self.candidates)-1 :
return
# 递归
for e in range(cur,len(self.candidates)):
if sum(l + [self.candidates[e]]) > self.target:
break;
#去重
if e > cur and self.candidates[e] == self.candidates[e-1]:
continue
self._combinationSum(e+1,l+ [self.candidates[e]])
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.candidates = sorted(candidates)
self.target = target
for i in range(len(candidates)):
if self.candidates[i] > self.target:
break;
# 去重
if i> 0 and self.candidates[i] == self.candidates[i-1]:
continue
self._combinationSum(i+1,[self.candidates[i]])
return self.ans
