题目地址
https://leetcode.com/problems/combination-sum/description/
题目描述
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]
]
思路
这道题目是求集合,并不是求极值
,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- backtrack 解题公式
代码
- 语言支持: Javascript,Python3
/* * @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:
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
- 46.permutations
- 47.permutations-ii
- 78.subsets
- 90.subsets-ii
- 113.path-sum-ii
- 131.palindrome-partitioning
给定一个已经 按绝对值升序排列 的数组,找到两个数使他们加起来的和等于特定数。函数应该返回这两个数的下标,index1必须小于index2。注意返回的值是0-based。请使用双指针完成本题,否则你有可能会被取消比赛资格。注意事项:```- 数据保证nums中的所有数的互不相同的。- nums数组长度≤100000- nums内的数≤1000000000``…
LeetCode题解371.sum-of-two-integers题目地址 https://leetcode.com/problems/sum-of-two-integers/description/ 题目描述 Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example 1: …
LeetCode题解113.path-sum-ii题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…
LeetCode题解15.3-sum题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…
LeetCode题解209.minimum-size-subarray-sum题目地址 https://leetcode.com/problems/minimum-size-subarray-sum/description/ 题目描述 Given an array of n positive integers and a positive integer s, find the minimal length of a contiguo…