LeetCode39-组合总数

这周三次考试

今天上午考完了一门

有意思的是：可以带电子产品考试

老师，你这是在赤裸裸的嘲讽我们吗？

哎，不说了

得看数学去了

等我把所有考试结束了

一定要给自己放个假好好耍耍

---

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]
]

思路：

本题和15-三数之和类似，但是本题的组合不是3个固定的，而是可以变化的，所以要比15题更难。采用的方法也是经常提起的回溯法，具体方法可以参考下面这篇文章

程小新同学：LeetCode--回溯法心得​zhuanlan.zhihu.com

具体代码见代码：

class Solution:
    # 本题和15. 三数之和类似，但是本题的组合不是3个固定的，而是可以变化的
    # 本题还是采用回溯法
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 定义接受符合要求答案的集合
        final_result = []

        def back(candidates, target, start=0, answer=[]):
            """
            :param candidates:
            :param target: int-->每次循环的目标值，随时变化
            :param start: int-->定义搜索的起始位置
            :param answer: List[int]-->定义存储临时答案
            :return:
            """
            if target == 0:
                final_result.append(answer)
                return
            for index in range(start, len(candidates)):
                if candidates[index] <= target:
                    new_target = target - candidates[index]
                    new_answer = []
                    new_answer.extend(answer)       
                    new_answer.append(candidates[index])
                    back(candidates, new_target, index, new_answer)

        back(candidates, target)
        return final_result


if __name__ == "__main__":
    candidates = [2,3,6,7]
    target = 8
    result = Solution().combinationSum(candidates, target)
    print(result)

执行效率也是挺快的，在90%左右。