组合总和1 中等🌟🌟🌟
问题描述
原文链接：39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
代码实现
Java
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTrack(candidates, target, 0, 0);
return res;
}
void backTrack(int[] candidates, int target, int index, int sum){
// 剪枝
if(sum > target){
return;
}
// 结束条件
if(sum == target){
res.add(new ArrayList<>(temp));
return;
}
// 处理主要逻辑
for(int i = index; i < candidates.length; i++){
// 从多个元素选择一个
temp.add(candidates[i]);
sum = sum + candidates[i];
backTrack(candidates, target, i, sum);
// 撤销之前的操作
temp.remove(temp.size() - 1);
sum = sum - candidates[i];
}
}
}
Python
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
temp = []
self.backTrack(candidates, target, 0, 0, temp, res)
return res
def backTrack(self, candidates, target, index, sum, temp, res):
# 剪枝
if sum > target:
return
# 结束条件
if sum == target:
res.append(list(temp))
return
# 处理主要逻辑
for i in range(index, len(candidates)):
# 从多个元素选择一个
temp.append(candidates[i])
sum += candidates[i]
self.backTrack(candidates, target, i, sum, temp, res)
# 撤销之前的操作
temp.pop()
sum -= candidates[i]
C++
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> temp;
backTrack(candidates, target, 0, 0, temp, res);
return res;
}
void backTrack(vector<int>& candidates, int target, int index, int sum, vector<int>& temp, vector<vector<int>>& res) {
// 剪枝
if (sum > target) {
return;
}
// 结束条件
if (sum == target) {
res.push_back(temp);
return;
}
// 处理主要逻辑
for (int i = index; i < candidates.size(); i++) {
// 从多个元素选择一个
temp.push_back(candidates[i]);
sum += candidates[i];
backTrack(candidates, target, i, sum, temp, res);
// 撤销之前的操作
temp.pop_back();
sum -= candidates[i];
}
}
};
Go
func combinationSum(candidates []int, target int) [][]int {
res := [][]int{}
temp := []int{}
backTrack(candidates, target, 0, 0, &temp, &res)
return res
}
func backTrack(candidates []int, target, index, sum int, temp *[]int, res *[][]int) {
// 剪枝
if sum > target {
return
}
// 结束条件
if sum == target {
copyTemp := make([]int, len(*temp))
copy(copyTemp, *temp)
*res = append(*res, copyTemp)
return
}
// 处理主要逻辑
for i := index; i < len(candidates); i++ {
// 从多个元素选择一个
*temp = append(*temp, candidates[i])
sum += candidates[i]
backTrack(candidates, target, i, sum, temp, res)
// 撤销之前的操作
*temp = (*temp)[:len(*temp)-1]
sum -= candidates[i]
}
}