0039. 组合总和 · ttttt

# 0039. 组合总和 ## 题目地址(39. 组合总和) <https://leetcode-cn.com/problems/combination-sum/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个无重复元素的数组 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 ``` ``` ## 前置知识 - 回溯法 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路这道题目是求集合，并不是`求极值`，因此动态规划不是特别切合，因此我们需要考虑别的方法。这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的 [通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，这里的所有的解法使用通用方法解答。除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。我们先来看下通用解法的解题思路，我画了一张图： ![](https://img.kancloud.cn/46/ec/46ec3382e572355e2109c47284e37e4b_1341x1080.jpg) > 图是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，仅做参考。通用写法的具体代码见下方代码区。 ## 关键点解析 - 回溯法 - backtrack 解题公式 ## 代码 - 语言支持: Javascript，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=39 lang=javascript * * [39] Combination Sum * * https://leetcode.com/problems/combination-sum/description/ * * algorithms * Medium (46.89%) * Total Accepted: 326.7K * Total Submissions: 684.2K * Testcase Example: '[2,3,6,7]\n7' * * Given a set of candidate numbers (candidates) (without duplicates) and a * target number (target), find all unique combinations in candidates where the * candidate numbers sums to target. * * The same repeated number may be chosen from candidates unlimited number of * times. * * Note: * * * All numbers (including target) will be positive integers. * The solution set must not contain duplicate combinations. * * * Example 1: * * * Input: candidates = [2,3,6,7], target = 7, * A solution set is: * [ * ⁠ [7], * ⁠ [2,2,3] * ] * * * Example 2: * * * Input: candidates = [2,3,5], target = 8, * A solution set is: * [ * [2,2,2,2], * [2,3,3], * [3,5] * ] * */ function backtrack(list, tempList, nums, remain, start) { if (remain < 0) return; else if (remain === 0) return list.push([...tempList]); for (let i = start; i < nums.length; i++) { tempList.push(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i); // 数字可以重复使用， i + 1代表不可以重复利用 tempList.pop(); } } /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function(candidates, target) { const list = []; backtrack(list, [], candidates.sort((a, b) => a - b), target, 0); return list; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: """ 回溯法，层层递减，得到符合条件的路径就加入结果集中，超出则剪枝；主要是要注意一些细节，避免重复等； """ size = len(candidates) if size <= 0: return [] # 先排序，便于后面剪枝 candidates.sort() path = [] res = [] self._find_path(target, path, res, candidates, 0, size) return res def _find_path(self, target, path, res, candidates, begin, size): """沿着路径往下走""" if target == 0: res.append(path.copy()) else: for i in range(begin, size): left_num = target - candidates[i] # 如果剩余值为负数，说明超过了，剪枝 if left_num < 0: break # 否则把当前值加入路径 path.append(candidates[i]) # 为避免重复解，我们把比当前值小的参数也从下一次寻找中剔除， # 因为根据他们得出的解一定在之前就找到过了 self._find_path(left_num, path, res, candidates, i, size) # 记得把当前值移出路径，才能进入下一个值的路径 path.pop() ``` ``` ## 相关题目 - [40.combination-sum-ii](40.combination-sum-ii.html) - [46.permutations](46.permutations.html) - [47.permutations-ii](47.permutations-ii.html) - [78.subsets](78.subsets.html) - [90.subsets-ii](90.subsets-ii.html) - [113.path-sum-ii](113.path-sum-ii.html) - [131.palindrome-partitioning](131.palindrome-partitioning.html)