LeetCode热题HOT100第十八天39.组合总和用python3求解

题目地址

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &＃xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &＃xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同&＃xff0c;则两种组合是不同的。

对于给定的输入&＃xff0c;保证和为 target 的不同组合数少于 150 个。

示例 1&＃xff1a;
输入&＃xff1a;candidates &＃61; [2,3,6,7], target &＃61; 7
输出&＃xff1a;[[2,2,3],[7]]
解释&＃xff1a;
2 和 3 可以形成一组候选&＃xff0c;2 &＃43; 2 &＃43; 3 &＃61; 7 。注意 2 可以使用多次。
7 也是一个候选&＃xff0c; 7 &＃61; 7 。
仅有这两种组合。

示例 2&＃xff1a;
输入: candidates &＃61; [2,3,5], target &＃61; 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3&＃xff1a;
输入: candidates &＃61; [2], target &＃61; 1
输出: []

提示&＃xff1a;
1 <&＃61; candidates.length <&＃61; 30
1 <&＃61; candidates[i] <&＃61; 200
candidate 中的每个元素都 互不相同
1 <&＃61; target <&＃61; 500

解题思路
变量意义&＃xff1a;use表示已经使用过的数&＃xff08;组成的列表&＃xff09;&＃xff0c;remain表示距离target还有多大。

对candidates升序排序&＃xff0c;以方便根据remain的大小使用return减小搜索空间&＃xff1b;

递归求可能的组合。
具体的&＃xff0c;每次递归时对所有candidates做一次遍历&＃xff0c;情况有3&＃xff1a;

1&＃xff0c;满足条件&＃xff0c;则答案加入一条&＃xff1b;
2&＃xff0c;不足&＃xff0c;继续递归&＃xff1b;
3&＃xff0c;超出&＃xff0c;则直接退出本路线。


注意每层递归都对全体candidates做遍历会导致如[2,2,3],[3,2,2]这样的对称重复的答案的产生。这是因为发生了“往前选择”的情况&＃xff0c;我们每次更深层的递归都往后缩小一个candidates&＃xff0c;强制函数只能“往后选择”&＃xff0c;这将不会出现重复答案。&＃xff08;体现在i的设计上&＃xff0c;每次递归find(i, use &＃43; [c], remain - c)都是从下标i开始&＃xff0c;而不是从下标0开始。也就是下一轮递归起始值是从candidates[i]开始&＃xff0c;而不是candidates[0]开始。

代码实现&＃xff1a;

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:candidates &＃61; sorted(candidates)ans &＃61; []def find(s, use, remain):for i in range(s, len(candidates)):c &＃61; candidates[i]if c &＃61;&＃61; remain:ans.append(use &＃43; [c])if c < remain:find(i, use &＃43; [c], remain - c)if c > remain:returnfind(0, [], target)return ans