关于leetcode:LeetCode-39-组合总和-Python

9次阅读

共计 1460 个字符，预计需要花费 4 分钟才能阅读完成。

题目起源：力扣（LeetCode）
https://leetcode-cn.com/problems/combination-sum

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

先审题，题目给定无反复元素数组和目标值 target，要求找出数组中所有能够使数组元素和为 target 的组合。

其中数组中的元素都为正整数，能够重复使用数组中的元素，然而解集中不能存在反复的组合。

这里能够看示例 1：

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

这里答案并没有 [2,3,2] 或 [3,2,2]，因为这两者就被视为与 [2,2,3] 为反复的组合，这里须要特地留神。

这里这里通过画图来阐明，以下是简略图例：

在这里 $\color{red}{✖}$ 示意不抉择此元素，这样就能够防止元素组合反复的状况，$\color{green}{✖}$ 示意以后门路抉择元素和大于目标值 target，而 $\color{green}{✔}$ 则示意以后门路抉择元素和等于目标值，能够将此组合增加到返回列表中。

在下面的图例中，只是简略画出了一个分支的状况，然而其余分支抉择的策略雷同，这里就省略了。若有不太明确的中央，倡议能够自行在草稿上进行补全，也帮忙本人了解。

那么就依照下面图例中的思路，用代码进行实现，具体如下。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 后果列表
        ans = []
        # 可能的组合
        tmp = []

        def helper(idx, total):
            """ 回溯，求组合总和
            Args:
                idx: 选取元素索引
                total: 组合中的元素和
            """
            # 基准条件
            # 当元素和大于目标值，间接返回
            if total > target:
                return
            # 当元素和等于目标值，将组合增加到后果中，返回
            if total == target:
                ans.append(tmp[::])
                return
            
            # 进入分支，同时防止反复组合
            for i in range(idx, len(candidates)):
                # 更新 total 值，total += candidates[i]
                # 同时将以后元素尝试增加到组合中
                tmp.append(candidates[i])
                # 再次进入递归
                # 这里能够看文章图例，递归向下，可选元素是从本身开始抉择
                # 这里同时也能防止组合反复，因为不会再次抉择索引 i 后面对应的元素
                helper(i, total)
                # 回溯，回退组合元素及 total 值
                tmp.pop()
                total -= candidates[i]
            
        total = 0
        helper(0, total)
        return ans

公众号【书所集录】

正文完