【Day 80 】2021-11-28 - 39 组合总和 #99
Comments
思路:列出所有的结果，经常需要用到回溯。 方法: 回溯(dfs)代码:实现语言: C++ class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> curGroup;
dfs(candidates, target, curGroup, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, vector<int>& curGroup, int sum, int startPos)
{
if (sum > target)
return;
if (sum == target)
res.push_back(curGroup);
else
{
int curSum = sum;
for (int i = startPos; i < candidates.size(); i++)
{
sum = curSum; // 保证sum不受同层元素的影响
sum = sum + candidates[i];
curGroup.push_back(candidates[i]);
dfs(candidates, target, curGroup, sum, i);
curGroup.pop_back();
}
}
}
};复杂度分析:
|
代码
C++ Code: class Solution {
public:
vector<vector<int>> res;
void dfs(vector<int>& temp, int target, vector<int>& candidates, int idx)
{
if(target==0)
res.push_back(temp);
else if(target>0)
{
for(int i=idx;i<candidates.size();i++)
{
temp.push_back(candidates[i]);
dfs(temp,target-candidates[i],candidates,i);
temp.pop_back();
}
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
if(target<candidates[0])
return {};
vector<int> temp;
dfs(temp, target, candidates,0);
return res;
}
};
|
Problem 39. Combination SumAlgorithm
Complexity
CodeLanguage: Java public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
LinkedList<Integer> comb = new LinkedList<>();
this.backtrack(target, comb, 0, candidates, results);
return results;
}
private void backtrack(int remain, LinkedList<Integer> comb, int start, int[] candidates, List<List<Integer>> results) {
if (remain == 0) {
results.add(new ArrayList<Integer>(comb));
return;
} else if (remain < 0) {
return;
}
for (int i = start; i < candidates.length; ++i) {
comb.add(candidates[i]);
this.backtrack(remain - candidates[i], comb, i, candidates, results);
comb.removeLast();
}
} |
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target == 0:
res.append(path)
return
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break
dfs(candidates, index, size, path + [candidates[index]], res, residue)
size = len(candidates)
if size == 0:
return []
candidates.sort()
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
|
思路
Java Codeclass Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList();
dfs(candidates, target, new ArrayList(), 0);
return res;
}
private void dfs(int[] candidates, int target, List<Integer> path, int index) {
if (target < 0) {
return;
}
if (target == 0) {
List<Integer> temp = new ArrayList(path);
res.add(temp);
return;
}
for (int i = index; i < candidates.length; i++) {
path.add(candidates[i]);
dfs(candidates, target - candidates[i], path, i);
path.remove(path.size() - 1);
}
}
}时间&空间
|
IdeaBacktracking. For each element we have two choices, include it in current list or not. For each choice, we need to remember the remainder we have. Then do the choice again for the candidates starting with current element with current remainder. If eventually the remainder is zero, we find one of the answers. The problem will create an N-ary tree, whose max height is T/M, where T is the target, M is the minimum value from the candidates. Thus the total nodes of the tree will be N^(T/M+1) Codeclass Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtracking(i, cur, remainder):
if i>= len(candidates) or remainder < 0:
return
if remainder == 0:
ans.append(cur)
return
backtracking(i, cur+[candidates[i]], remainder-candidates[i])
backtracking(i+1, cur, remainder)
ans = []
backtracking(0, [], target)
return ansComplexityTime: O(N^(T/M+1)) |
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
if (idx == candidates.size()) {
return;
}
if (target == 0) {
ans.emplace_back(combine);
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> combine;
dfs(candidates, target, ans, combine, 0);
return ans;
}
}; |
思路
关键点代码
C++ Code: class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> onePath;
vector<vector<int>> ret;
int sum =0;
backTrac(candidates, target, sum, 0, onePath, ret);
return ret;
}
void backTrac(vector<int>& candidate, int target, int sum, int start, vector<int>& onePath, vector<vector<int>>& ret)
{
if(sum == target)
{
ret.push_back(onePath);
return;
}
if(sum > target)
return;
if(start>=candidate.size())
return;
for(int i=start; i< candidate.size(); i++)
{
sum += candidate[i];
onePath.push_back(candidate[i]);
backTrac(candidate, target, sum, i, onePath, ret);
onePath.pop_back();
sum -= candidate[i];
}
}
};
|
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if candidates is None:
return []
result = []
candidates.sort()
self.dfs(candidates, result, [], target, 0)
return result
def dfs(self, candidates, result, sub, target, index):
if target == 0:
result.append(list(sub))
return
for i in range(index, len(candidates)):
if candidates[i] > target:
break
sub.append(candidates[i])
self.dfs(candidates, result, sub, target - candidates[i], i)
sub.pop() |
|
Backtracking. class Solution:
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
N = len(nums)
nums.sort()
ret = []
def dfs(idx, sum, path):
if idx == N: return
if sum > target: return
if sum == target:
nonlocal ret
ret.append(list(path))
return
dfs(idx+1, sum, path)
path.append(nums[idx])
dfs(idx, sum+nums[idx], path)
path.pop()
dfs(0, 0, [])
return ret |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
dfs(candidates, target, 0, new ArrayList<>(), res, 0);
return res;
}
private void dfs(int nums[], int target, int idx, List<Integer> build, List<List<Integer>> res, int sum) {
if (sum == target) {
res.add(new ArrayList<>(build));
return;
} else if (idx == nums.length) {
return;
}
for (int i = 0; sum + i * nums[idx] <= target; ++i) {
for (int j = 0; j < i; ++j) {
build.add(nums[idx]);
}
dfs(nums, target, idx + 1, build, res, sum + i * nums[idx]);
for (int j = 0; j < i; ++j) {
build.remove(build.size() - 1);
}
}
}
} |
var combinationSum = function(candidates, target) {
let res = [];
const l = candidates.length;
var dfs = (cur_sum, cur_items, index) => {
if (cur_sum == target){
let newIn = [];
for (let item of cur_items){newIn.push(item)};
res.push(newIn);
}else if (cur_sum < target){
for (let j=index; j<l; j++){
cur_items.push(candidates[j]);
dfs(cur_sum+candidates[j], cur_items, j);
cur_items.pop();
};
};
};
for (let i=0; i<l; i++){
dfs(candidates[i], [candidates[i]], i);
};
return res;
};class Solution(object):
def combinationSum(self, candidates, target):
length = len(candidates)
result = []
def dfs(cur_sum, index, cur_items):
if cur_sum == target:
result.append(deepcopy(cur_items))
if cur_sum > target:
return
else:
for i in range(index, length):
dfs(cur_sum+candidates[i], i, cur_items+[candidates[i]])
for i in range(length):
dfs(candidates[i], i, [candidates[i]])
return result |
link:https://leetcode.com/problems/combination-sum/submissions/ 代码 Javascriptfunction combinationSum(candidates, target) {
var buffer = [];
var result = [];
search(0, target);
return result;
function search(startIdx, target) {
if (target === 0) return result.push(buffer.slice());
if (target < 0) return;
if (startIdx === candidates.length) return;
buffer.push(candidates[startIdx]);
search(startIdx, target - candidates[startIdx]);
buffer.pop();
search(startIdx + 1, target);
}
} |
回溯经典回溯问题 需要学习整个回溯的写法，套上模板就可以 https://leetcode.com/problems/combination-sum/ 代码class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.ans = []
size = len(candidates)
def backtrack(curSum, start, path):
if curSum == target:
self.ans.append(path[:])
return
for i in range(start, size):
if candidates[i]+curSum > target:
continue
if candidates[i] > target:
continue
backtrack(curSum+candidates[i], i, path+[candidates[i]])
backtrack(0, 0, [])
return self.ans |
解题思路回溯+剪枝。参考官方题解。因为数字可以无限制重复被选取，所以要用回溯，考虑所有情况。回溯过程中我们可以剪掉sum超过target的情况，如果遇到sum等于target，我们就将现有的符合条件的组合存到结果的List中。为了去重，规定每一个递归树的节点的子节点不能取在candidates数组中出现在该节点之前的元素。 代码class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backtrack(0, target, candidates, list, res);
return res;
}
private void backtrack(int pos, int cur, int[] candidates, List<Integer> list, List<List<Integer>> result) {
// if sum is equal to target, one route is found
if (cur == 0) {
result.add(new ArrayList<>(list)); // cannot use list here, need to specify the type (new ArrayList<>())
return;
}
// if sum is greater than target
if (cur < 0) {
return;
}
// if sum is smaller than target, continue backtracking
// can only peak elements which showed up at the current index or later to avoid duplication
for (int i = pos; i < candidates.length; i++) {
list.add(candidates[i]);
backtrack(i, cur - candidates[i], candidates, list, result);
list.remove(list.size() - 1);
}
}
}复杂度分析
|
思路这个题目其实就是背包问题的展开式，背包问题一般只要求返回最优解的长度/个数，但这个要求把具体的解展开 因此思路有两个方向，沿用dp和回溯+剪枝
代码class Solution:
# 动规解法
def combinationSum1(self, candidates: List[int], target: int) -> List[List[int]]:
dp = [[[]]] + [[] for _ in range(target)]
for i in range(len(candidates)):
for j in range(candidates[i], target + 1):
if dp[j - candidates[i]]:
dp[j] += [tmp + [candidates[i]] for tmp in dp[j - candidates[i]]]
return dp[-1]
# 回溯+剪枝解法(比动规更好)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates.sort()
def dfs(target, cur_ans, candidates):
if target == 0:
ans.append(cur_ans)
return
for i, c in enumerate(candidates):
if c > target:
break
dfs(target - c, cur_ans + [c], candidates[i:])
dfs(target, [], candidates)
return ans |
Problemhttps://leetcode.com/problems/combination-sum/ Solutionclass Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if(candidates == null || candidates.length == 0){
return res;
}
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
helper(candidates, 0, target, list, res);
return res;
}
private void helper(int[] nums, int start, int remain, List<Integer> list, List<List<Integer>> res){
if(remain == 0){
res.add(new ArrayList<>(list));
return;
}
if(remain < 0 || start == nums.length){
return;
}
for(int i = start; i < nums.length; i++){
if(nums[i] <= remain){
list.add(nums[i]);
helper(nums, i, remain - nums[i], list, res);
list.remove(list.size() - 1);
}else{
return;
}
}
}
}Complexity
|
思路这个题目其实就是背包问题的展开式，背包问题一般只要求返回最优解的长度/个数，但这个要求把具体的解展开 因此思路有两个方向，沿用dp和回溯+剪枝
代码class Solution:
# 动规解法
def combinationSum1(self, candidates: List[int], target: int) -> List[List[int]]:
dp = [[[]]] + [[] for _ in range(target)]
for i in range(len(candidates)):
for j in range(candidates[i], target + 1):
if dp[j - candidates[i]]:
dp[j] += [tmp + [candidates[i]] for tmp in dp[j - candidates[i]]]
return dp[-1]
# 回溯+剪枝解法(比动规更好)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates.sort()
def dfs(target, cur_ans, candidates):
if target == 0:
ans.append(cur_ans)
return
for i, c in enumerate(candidates):
if c > target:
break
dfs(target - c, cur_ans + [c], candidates[i:])
dfs(target, [], candidates)
return ans |
思路回溯。 代码(C++)class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) res.push_back(path);
for (int i = startIndex; i < candidates.size(); i++) {
if (sum + candidates[i] > target) continue;
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
path.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, target, 0, 0);
return res;
}
};复杂度分析
|
39. Combination Sumhttps://leetcode.com/problems/combination-sum/ Topics-Backtracking 思路Backtracking 代码 Pythonclass Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dp(combination, val_left, indx):
if val_left == 0:
res.append(combination[:])
return
for i in range(indx, len(candidates)):
if candidates[i] <= val_left:
combination.append(candidates[i])
dp(combination, val_left - candidates[i], i)
combination.pop()
candidates.sort()
res = []
dp([], target, 0)
return res复杂度分析Let N be the number of candidates, T be the target value, and M be the minimal value among the candidates. |
|
回溯 + 深度DFS func combinationSum(candidates []int, target int) [][]int {
if len(candidates) == 0{
return nil
}
out := [][]int{}
var dfs func(start int,sum int,path []int)
dfs = func(start int,sum int,path []int){
if sum >= target{
if sum == target{
temp := make([]int,len(path))
copy(temp,path)
out = append(out,temp)
}
return
}
for i:=start;i<len(candidates);i++{
path = append(path,candidates[i])
dfs(i,sum+candidates[i],path)
path = path[:len(path)-1]
}
}
dfs(0,0,[]int{})
return out
}时间复杂度O(2^n) |
thoughtsDFS 回溯所有解 遇到大于target的可以不用进行下去 codeclass Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
results = []
single_solution = []
def dfs(index, temp_sum):
if temp_sum < target:
for i in range(index, len(candidates)):
single_solution.append(candidates[i])
dfs(i, temp_sum + candidates[i])
single_solution.pop()
elif temp_sum == target:
results.append(list(single_solution))
dfs(0, 0)
return resultscomplexityTime O(2^n) |
代码class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result=[]
path=[]
def backtracking(index,current_sum):
if current_sum == target:
result.append(path.copy())
return
if current_sum > target:
return
for i in range(index,len(candidates)):
path.append(candidates[i])
backtracking(i,current_sum+candidates[i])
path.pop()
backtracking(0,0)
return result复杂度Time: (N^(T/M+1)) T is the target, M is the min number Space: O(n) |
代码class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(ans,tempList, candidates, remain, start):
if remain < 0: return
elif remain == 0: return ans.append(tempList.copy())
for i in range(start, len(candidates)):
tempList.append(candidates[i])
backtrack(ans, tempList, candidates, remain - candidates[i], i)
tempList.pop()
ans = [];
backtrack(ans, [], candidates, target, 0);
return ans; |
思路直接使用回溯方法会有一个问题, 因为没有去重复, 所以 [2,2,3] 和 [3,2,2] 会是不同的回溯组合, 会大大增加时间复杂度, 并且答案也需要再次去重又增加了复杂度 所以希望在搜索的过程中就不要产生重复的元素, 方法是每次搜索的时候限制只能使用元素本身和之后的元素 eg. 元素是 [2,3,4] 在 index = 0 的时候可以使用 [2,3,4], 在 index = 1 的时候只能使用 [3,4] 这样避免了 [3,2,2] 和 [2,2,3] 这样的重复组合出现 每次如果 num == 0 是base case, 代表已经找到了一个符合条件的组合, 那么就添加到 res 水煮鱼中 否则根据上面的分析使用从 index 开始的 candidates (包含 index 本身因为允许每个数字允许使用无数次), 每次如果 num-c ≥ 0, 代表有可能可以使用这个 candidate c, 那么继续 dfs, 使用 c 时从 c 的 index 开始, 因为避免再次使用前面的数字造成重复, 使用前面数字的 case 在前面都已经被 cover 了 class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(num, cur, index):
if num == 0:
res.append(cur)
return
for i,c in enumerate(candidates):
if i < index:
continue
if num - c >= 0:
dfs(num-c, cur+[c],i)
dfs(target, [], 0)
return res复杂度时间复杂度: O(n^(target/min)) n 为 candidates 的长度, target/min 是递归栈的最大深度, 这是很宽松的上届, 因为可能有的值很大搜索次数就很少, 并且加上剪枝搜索次数会更少 空间复杂度: O(target/min) 递归栈的深度最大是 target/min, 并且 记录 path 上节点的 list 的长度也不大于 target/min |
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& c, int target) {
dfs(c, 0, target);
return ans;
}
void dfs(vector<int>& c, int u, int target) {
if (target == 0) {
ans.push_back(path);
return;
}
if (u == c.size()) return;
for (int i = 0; c[u] * i <= target; i ++ ) {
dfs(c, u + 1, target - c[u] * i);
path.push_back(c[u]);
}
for (int i = 0; c[u] * i <= target; i ++ ) {
path.pop_back();
}
}
}; |
代码块var combinationSum = function (candidates, target) {
const ans = [];
const dfs = (target, combine, idx) => {
if (idx == candidates.length) {
return;
}
if (target === 0) {
ans.push(combine);
return;
}
dfs(target, combine, idx + 1);// 直接跳过
// 选择当前的数据
if (target - candidates[idx] >= 0) {
dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
}
}
dfs(target, [], 0);
return ans;
};时间复杂度和空间复杂度
|
|
/**
|
39. 组合总和// 11-28 cpp 剪枝
class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
void backtrack(vector<int> &candidates, int target, int sum, int startidx) {
// 终止条件
if (sum == target) {
ans.push_back(temp);
return;
}
// 剪枝
for (int i = startidx; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
temp.push_back(candidates[i]);
//由于每一个元素可以重复使用，下一轮搜索的起点依然是 i
backtrack(candidates, target, sum, i);
// 回溯
sum -= candidates[i];
temp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int len = candidates.size();
sort(candidates.begin(),candidates.end()); //排序
backtrack(candidates, target, 0, 0);
return ans;
}
}; |
思路回溯 代码class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res复杂度
|
思路See Comments 代码class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& v, vector<int>& candidates,int curr, int pos) {
// case if cannot be added up to target
if (curr < 0) return;
// answer vector found
if (curr == 0) {
res.push_back(v);
return;
}
// pos for not giving repeating answer combos
for (int i = pos; i < candidates.size(); ++i) {
v.push_back(candidates[i]);
backtrack(res, v, candidates, curr - candidates[i], i);
v.pop_back(); // recover
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> v;
backtrack(res, v, candidates, target, 0);
return res;
}
};时间复杂度 O(n^target/min)空间复杂度 O(target/min) |
|
class Solution { } |
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res= []
can = sorted(list(set(candidates)))
n = len(can)
def dfs(can, path, startindex, remain):
if remain==0:
res.append(path[:])
for i in range(startindex, n):
if can[i]>remain: #用来剪枝加速
break
path.append(can[i])
dfs(can,path,i,remain-can[i])
path.pop()
dfs(can,[],0,target)
return res |
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
} |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
LinkedList<Integer> comb = new LinkedList<>();
this.backtrack(target, comb, 0, candidates, results);
return results;
}
private void backtrack(int remain, LinkedList<Integer> comb, int start, int[] candidates, List<List<Integer>> results) {
if (remain == 0) {
results.add(new ArrayList<Integer>(comb));
return;
} else if (remain < 0) {
return;
}
for (int i = start; i < candidates.length; ++i) {
comb.add(candidates[i]);
this.backtrack(remain - candidates[i], comb, i, candidates, results);
comb.removeLast();
}
}
} |
思路完全无剪枝版本：记录下所有结果(list sort后toString(),缓存到Hash表里), 去重后返回结果 通过控制索引剪掉重复结果 数组排序后，判断如果target-num<0就终止遍历从而进一步剪枝 代码： class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
LinkedList<Integer> ret = new LinkedList<>();
Arrays.sort(candidates);
dfs(candidates,target,ret,0);
return ans;
}
private void dfs(int[] candidates, int target,LinkedList<Integer> ret,int idx) {
if(target == 0){
ans.add(new ArrayList(ret));
return;
}
for(int i=idx;i<candidates.length;i++){
int num = candidates[i];
ret.add(num);
boolean valid = target - num >= 0;
if(valid){
dfs(candidates,target-num,ret,i);
}
ret.removeLast();
//排序后的数组可以直接剪枝
if(!valid)break;
}
}
}
|
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res, cur = [], []
candidates.sort()
self.dfs(candidates, target, 0, cur, res)
return res
def dfs(self, candidates, target, s, cur, res):
if target == 0:
res.append(cur.copy())
return
for i in range(s, len(candidates)):
if candidates[i] > target: break
cur.append(candidates[i])
self.dfs(candidates, target - candidates[i], i, cur, res)
cur.pop() |
思路
代码class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
public void dfs(int[] candidates, int begin, int length, int target, Deque path, List<List<Integer>> res) {
// 递归结束的条件， 当前的值 为0的时候，
if (target < 0) return ;
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for(int i = begin;i < length;i++) {
path.addLast(candidates[i]);
dfs(candidates, i, length, target - candidates[i], path, res);
path.removeLast();
}
}
}复杂度
|
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
dfs(result, new ArrayList<>(), candidates, 0, 0, target);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> sub, int[] nums, int startIndex, int sum, int target){
if (sum == target){
result.add(new ArrayList<>(sub));
return;
}
for (int i = startIndex; i < nums.length; i++){
if (sum + nums[i] > target) continue;
sub.add(nums[i]);
dfs(result, sub, nums, i, sum + nums[i], target);
sub.remove(sub.size() - 1);
}
}
} |
|
|
public List<List> combinationSum(int[] candidates, int target) { private void backtrack(int remain, LinkedList comb, int start, int[] candidates, List<List> results) { |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
dfs(result, new ArrayList<>(), candidates, 0, 0, target);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> sub, int[] nums, int startIndex, int sum, int target){
if (sum == target){
result.add(new ArrayList<>(sub));
return;
}
for (int i = startIndex; i < nums.length; i++){
if (sum + nums[i] > target) continue;
sub.add(nums[i]);
dfs(result, sub, nums, i, sum + nums[i], target);
sub.remove(sub.size() - 1);
}
}
} |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
dfs(result, new ArrayList<>(), candidates, 0, 0, target);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> sub, int[] nums, int startIndex, int sum, int target){
if (sum == target){
result.add(new ArrayList<>(sub));
return;
}
for (int i = startIndex; i < nums.length; i++){
if (sum + nums[i] > target) continue;
sub.add(nums[i]);
dfs(result, sub, nums, i, sum + nums[i], target);
sub.remove(sub.size() - 1);
}
}
} |
【Day 80】39 组合总和代码class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
if (idx == candidates.size()) {
return;
}
if (target == 0) {
ans.emplace_back(combine);
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> combine;
dfs(candidates, target, ans, combine, 0);
return ans;
}
};复杂度时间复杂度：最坏情况：O(N*2^N) 空间复杂度：O(N) |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
dfs(candidates, target, ans, combine, idx + 1);
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
} |
|
title: "Day 80 39. 组合总和" 39. 组合总和题目给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 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]]
示例 3：
输入: candidates = [2], target = 1
输出: []
示例 4：
输入: candidates = [1], target = 1
输出: [[1]]
示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500题目思路
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
if (idx == candidates.size()) return;
if (target == 0) {
ans.emplace_back(combine);
return;
}
dfs(candidates, target, ans, combine, idx + 1);
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> combine;
dfs(candidates, target, ans, combine, 0);
return ans;
}
};复杂度
|
|
回溯 /**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
let res = [];
let dfs = (candidates, target, temp, index) => {
if (target === 0) {
res.push(temp.slice())
} else if (target > 0) {
for(let i = index; i < candidates.length; i++) {
temp.push(candidates[i]);
dfs(candidates, target - candidates[i], temp, i)
temp.pop()
}
}
}
dfs(candidates, target, [], 0)
return res
}; |
|
class Solution { } |
回溯const combinationSum = (candidates, target) => {
const res = [];
const dfs = (start, temp, sum) => {
if (sum >= target) {
if (sum == target) {
res.push(temp.slice());
}
return;
}
for (let i = start; i < candidates.length; i++) {
temp.push(candidates[i]);
dfs(i, temp, sum + candidates[i]);
temp.pop();
}
};
dfs(0, [], 0);
return res;
}
|
Codesconst combinationSum = (candidates, target) => {
const len = candidates.length;
const res = [];
candidates.sort((a, b) => a - b);
const search = (path, target, start) => {
if (target === 0) {
res.push([...path]);
return;
}
for (let i = start; i < len; i++) {
if (target < candidates[i]) return;
path.push(candidates[i]);
search(path, target - candidates[i], i);
path.pop();
}
};
search([], target, 0);
return res;
}; |
|
class Solution: |
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
dfs(candidates, target, 0, new ArrayList<>(), res, 0);
return res;
}
private void dfs(int nums[], int target, int idx, List<Integer> build, List<List<Integer>> res, int sum) {
if (sum == target) {
res.add(new ArrayList<>(build));
return;
} else if (idx == nums.length) {
return;
}
for (int i = 0; sum + i * nums[idx] <= target; ++i) {
for (int j = 0; j < i; ++j) {
build.add(nums[idx]);
}
dfs(nums, target, idx + 1, build, res, sum + i * nums[idx]);
for (int j = 0; j < i; ++j) {
build.remove(build.size() - 1);
}
}
}
} |
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(ans,tempList, candidates, remain, start):
if remain < 0: return
elif remain == 0: return ans.append(tempList.copy()) # 将部分解空间合并到总体的解空间
# 枚举所有以 i 为开始的部分解空间
for i in range(start, len(candidates)):
tempList.append(candidates[i])
backtrack(ans, tempList, candidates, remain - candidates[i], i)# 数字可以重复使用
tempList.pop()
ans = [];
backtrack(ans, [], candidates, target, 0);
return ans; |
思路回溯 代码void backtrace(int start, vector<int>& candidates, int target, int& sum, vector<int>& sumArray, vector<vector<int>>& res) {
if (sum >= target) {
if (sum == target)
res.push_back(sumArray);
return ;
}
for (int i = start; i < candidates.size(); ++i) {
sumArray.push_back(candidates[i]);
sum += candidates[i];
backtrace(i, candidates, target, sum, sumArray, res);
sum -= candidates[i];
sumArray.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> sumArray;
int sum = 0;
sort(candidates.begin(), candidates.end());
backtrace(0, candidates, target, sum, sumArray, res);
return res;
} |
思路字符串枚举 代码class Solution:
def strStr(self, haystack, needle):
if not needle:
return 0
left = 0
right = len(needle)
while right <= len(haystack):
if haystack[left:right] == needle:
return left
left += 1
right += 1
return -1复杂度
|
|
思路 实现语言: C++
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> curGroup;
dfs(candidates, target, curGroup, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, vector<int>& curGroup, int sum, int index)
{
if (sum > target)
return;
if (sum == target)
res.push_back(curGroup);
else
{
for (int i = index; i < candidates.size(); i++)
{
curGroup.push_back(candidates[i]);
dfs(candidates, target, curGroup, sum + candidates[i], i);
curGroup.pop_back(); //清空方便下次从头计算
}
}
}
};复杂度分析 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
39 组合总和
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/combination-sum/
前置知识
题目描述
The text was updated successfully, but these errors were encountered: