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)