[leetcode] 39/40 Combination sum

leetcode 39

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.

这里有几个注意点

1. 他这个题， 组合数选取 是有放回的， 简单说就是 每个数可以重复选择无数次。
2. candidate 不一定是有序的
3. solution 在元素层面上不允许重复， 比如 candidate=[2,3,4] ，[2,2,3]和 [2,3,2]是相同的, 就是 你选完当前的数， 你只能选从当前的数往后选， 不能往前选。
4. 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        

image.png

可以发现，递归所有情况速度会很慢，
如果这个 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  

image.png

组合数的和 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]])
# 有放回

2. 去重
   比如[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  

image.png