# [LeetCode] 39. Combination Sum 组合之和

2021年09月15日 阅读数：1

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`.html

The same repeated number may be chosen from `candidates` unlimited number of times.java

Note:python

• 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:app

```Input: candidates = [2,3,5]`, `target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]```

• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

Java：htm

```public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null) return res;
Arrays.sort(candidates);
getCombinations(res, new ArrayList<>(), candidates, target, 0);
return res;
}

private void getCombinations(List<List<Integer>> res, List<Integer> list, int[] nums, int target, int pos) {
if (target < 0) return;
if (target == 0) {
return;
}
for (int i = pos; i < nums.length; i++) {
if (nums[i] > target) break;
if (i > pos && nums[i] == nums[i - 1]) continue;
getCombinations(res, list, nums, target - nums[i], i);
list.remove(list.size() - 1);
}
}
}
```

Python:

```class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
result = []
self.combinationSumRecu(sorted(candidates), result, 0, [], target)
return result

def combinationSumRecu(self, candidates, result, start, intermediate, target):
if target == 0:
result.append(list(intermediate))
while start < len(candidates) and candidates[start] <= target:
intermediate.append(candidates[start])
self.combinationSumRecu(candidates, result, start, intermediate, target - candidates[start])
intermediate.pop()
start += 1　　```

Python: wo

```class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
self.helper(res, sorted(candidates), [], 0, 0, target)
return res

def helper(self, res, candidates, cur, temp, pos, target):
if temp > target:
return
if temp == target:
res.append(cur)

for i in range(pos, len(candidates)):
self.helper(res, candidates, cur + [candidates[i]], temp + candidates[i], i, target)　　```

C++:

```class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
// 注意candidates不是有序的，要先排序处理
sort(candidates.begin(), candidates.end());
// 用以记录答案和当前方案
vector<vector<int>> ans;
vector<int> current;
// 开始回溯搜索
backtracking(ans, candidates, current, 0, target);
// 返回答案
return ans;
}

void backtracking(vector<vector<int>>& ans, vector<int>& candidates, vector<int> current, int last_use, int rest_target) {
// 当rest_target等于0时，说明已经找到了一组合法的方案
if (rest_target == 0) {
// 故将其加入到答案当中
ans.push_back(current);
}
// 不然就枚举下一个加入到current中的数，在枚举中注意2个条件
// i >= last_use，保证current是非递减的
// candidates[i] <= rest_target，保证rest_target不小于0
for (int i = last_use; i < candidates.size() && candidates[i] <= rest_target; i++) {
// 放入current中
current.push_back(candidates[i]);
// 继续搜索下一个数字
backtracking(ans, candidates, current, i, rest_target - candidates[i]);
// 回溯处理
current.pop_back();
}
}
};
```

[LeetCode] 40. Combination Sum II 组合之和 II

[LeetCode] 216. Combination Sum III 组合之和 III

[LeetCode] 377. Combination Sum IV 组合之和 IV

[LeetCode] 78. Subsets 子集合

[LeetCode] 90. Subsets II 子集合 II

[LeetCode] 46. Permutations 全排列

[LeetCode] 47. Permutations II 全排列 II

[LeetCode] 131. Palindrome Partitioning 回文分割