组合

39. 组合总和

给定一个无重复元素的数组candidates 和一个目标数 target，找出candidates中所有可以使数字和为target的组合。
candidates 中的数字可以无限制重复被选取。
说明：

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

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

本题的总体思路是回溯+剪枝

• 以 target = 7 为根结点，每一个分支做减法。
• 减到 0 或者负数的时候，剪枝。其中，减到 0 的时候结算，这里 “结算” 的意思是添加到结果集。

上图说明：
一个蓝色正方形表示的是 “尝试将这个数到数组 candidates 中找组合”，那么怎么找呢？挨个减掉那些数就可以了。

• 在减的过程中，会得到 0 和负数，也就是被我标红色和粉色的结点：

• • 得到 0 是我们喜欢的，从 0 这一点向根结点走的路径（很可能只走过一条边，也算一个路径），就是一个组合，在这一点要做一次结算（把根结点到 0 所经过的路径，加入结果集）。
• • 得到负数就说明这条路走不通，没有必要再走下去了。

总结一下：在减的过程中，得到 0 或者负数，就没有必要再走下去，所以这两种情况就分别表示成为叶子结点。此时递归结束，然后要发生回溯。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        # 先将candidates进行排序，避免后面剪枝的时候出现如[2, 2, 3], [2, 3, 2]这样的重复路径
        # 要排序的理由：1、前面用过的数后面不能再用；2、下一层边上的数不能小于上一层边上的数。
        candidates.sort()
        res=[]
        path=[]
        n=len(candidates)
        def dfs(start,target):
            # 递归终止条件，Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
            if target==0:
                print(path)
                print(path[:])
                res.append(path[:])
            for i in range(start,n):
                tmp= target-candidates[i]
                if tmp<0:break
                path.append(candidates[i])
                # 因为下一层不能比上一层还小，起始索引还从 index 开始
                dfs(i,tmp)
                path.pop()
        dfs(0,target)
        return res

40. 组合总和 II

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

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

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

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

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

思路

• 本题和上题的区别在于candidates中的元素不可重复使用
• 因此只需要在递归的时候每层dfs从下一个元素开始即可
• 因为本身candidates中有重复元素，因此path在加入res之前需要查重

话不多说，show you the code

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        res=[]
        path=[]
        candidates.sort()
        n=len(candidates)

        def dfs(start,target):
            #与上题区别一、 去重
            if target==0 and path[:] not in res:
                res.append(path[:])
            for i in range(start,n):
                tmp=target-candidates[i]
                if tmp<0:
                    break
                path.append(candidates[i])
                #与上题区别二、 从下一个元素开始dfs
                dfs(i+1,tmp)
                path.pop()
        dfs(0,target)
        return res

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。
  示例 1:

  输入: k = 3, n = 7
  输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

• 本题和前两题的区别在于candidates变成了[1,2,3,4,5,6,7,8,9],且path长度只能是k,candidates不可重复使用
• 因此只需要在递归的时候每层dfs从下一个元素开始即可，并且在加入path之前，确认path的长度是否为k

话不多说，show you the code

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        # 排除k=0,n=0和k<n的情况
        if k==0 or n==0 or k>n:
            return []
        res,path=[],[]
        def helper(start,target):
            # 当此时target=0且path长度为k时，加入path
            if target==0 and len(path)==k:
                res.append(path[:])
            for i in range(start,10):
                tmp=target-i
                # 剪枝
                if tmp<0:
                    break
                path.append(i)
                # 从下一个开始继续dfs
                helper(i+1,tmp)
                print(path,i)
                path.pop()
        helper(1,n)
        return res

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/11/21/组合/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！