组合总和

给定一个无重复元素的数组 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]
]
 

提示:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum

思路:解决该问题,我们可以先考虑解决一个小问题,怎么求解任意的组合数,首先我们可以知道的是,对于每一次的选择的过程,我们可以将其看作成一颗二叉树,每一个节点就是一种情况,因为不能有重复的情况(顺序问题),所以我们不难想到可以使用回溯算法解决该问题。
回溯算法:回溯是经过修改的深度优先查找方法,是在树中查找。

# 给定数 n 和 k 求其组合情况(Cnk的形式)
def resolution(n):
    nums = [i for i in range(1, n+1)]
    res = []

    def backTrace(curr_nums, index):
        if len(curr_nums) == k:
            return res.append(curr_nums[:])
        for i in range(index, len(nums)):
            curr_nums.append(nums[i])
            backTrace(curr_nums, i + 1)
            curr_nums.pop()

    backTrace([], 0)
    print(res)


n = 4
k = 2
resolution(n)

解决该题的话,只需要稍微修改一点代码即可,更改一下回溯条件即可(不剪枝情况)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backTrace(curr_nums, index):
            if sum(curr_nums) == target: # 更改条件
                return res.append(curr_nums[:])
            if len(curr_nums) > (target / min(candidates)):  #增加结束条件
                return
            for i in range(index, len(candidates)):
                curr_nums.append(candidates[i])
                backTrace(curr_nums, i)
                curr_nums.pop()
        res = []
        backTrace([], 0)
        return res

因为没有剪枝的关系,以上的算法效率极低,下面这个是含有剪枝的代码:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i, tmp_sum, tmp):
            if  tmp_sum > target or i == n:
                return 
            if tmp_sum == target:
                res.append(tmp)
                return 
            for j in range(i, n):
                if tmp_sum + candidates[j] > target:  # 剪枝
                    break
                backtrack(j,tmp_sum + candidates[j],tmp+[candidates[j]])
        backtrack(0, 0, [])
        return res
点赞

发表评论

Title - Artist
0:00