Open azl397985856 opened 1 year ago
回溯,升序,记录位置
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;
**复杂度分析**
- 时间复杂度:
- 空间复杂度:
深度优先搜索
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(tar,cur,cur_list):
if tar<0:
return
if tar==0:
res.append(cur_list.copy())
return
for i in range(cur,len(candidates)):
cur_list.append(candidates[i])
dfs(tar-candidates[i],i,cur_list)
cur_list.pop()
dfs(target,0,[])
return res
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def dfs(start, num, vec):
if num == 0:
res.append(vec)
return
if start >= n or num < 0:
return
for i in range(start, n):
num = num - candidates[i]
dfs(i, num, vec + [candidates[i]])
num = num + candidates[i]
dfs(0, target, [])
return res
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
candidates.sort((a, b) => a - b);
const res = []; const path = []
const backtracking = (startIndex, sum) => {
if (sum === target) {
res.push([...path]);
return
}
if (sum > target) return
for (let i = startIndex; i < candidates.length; i++) {
path.push(candidates[i])
backtracking(i, sum + candidates[i]);
path.pop()
}
}
backtracking(0, 0);
return res
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target, int cur, int startindex)
{
if (cur >= target)
{
if (cur == target)
res.push_back(path);
else
return;
}
for (int i = startindex; i < candidates.size(); i++)
{
path.push_back(candidates[i]);
backtrack(candidates, target, cur + candidates[i], i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtrack(candidates, target, 0, 0);
return res;
}
};
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
var res = [];
var backTrack = (path,index) => {
var sum = path.reduce((cur, next) => cur + next, 0)
if (sum >= target) {
sum === target && res.push(path)
return
}
for (let j = index; j < candidates.length; j++) {
path.push(candidates[j])
backTrack(path.concat(), j)
path.pop()
}
}
backTrack([], 0)
return res
};
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret = []
self.dfs(candidates, target, [], ret)
return ret
def dfs(self, nums, target, path, ret):
if target < 0:
return
if target == 0:
ret.append(path)
return
for i in range(len(nums)):
self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
return dfs(candidates, 0, target, new ArrayDeque<>(), new ArrayList<>());
}
private List<List<Integer>> dfs(int[] candidates, int idx, int target, Deque<Integer> path, List<List<Integer>> ans) {
if (target == 0) {
ans.add(new ArrayList<>(path));
return ans;
}
for (int i = idx; i < candidates.length; i++) {
if (target < candidates[i]) break;
path.addFirst(candidates[i]);
dfs(candidates, i, target - candidates[i], path, ans);
path.removeFirst();
}
return ans;
}
class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates,target,0);
return ans;
}
void dfs(vector<int>& candidates, int target,int idx){
if(target==0) {
ans.push_back(temp);
return;
}
if(idx==candidates.size()) {
return;
}
dfs(candidates, target,idx+1);
if(target-candidates[idx]>=0){
temp.push_back(candidates[idx]);
dfs(candidates,target-candidates[idx],idx);
temp.pop_back();
}
}
};
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;
复杂度分析
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> combine = new ArrayList<>();
dfs(candidates, target, res, combine, 0);
return res;
}
public void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(combine));
return;
}
// 跳过当前数
dfs(candidates, target, res, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], res, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
self.backtrack(candidates, target, 0, [], res)
return res
def backtrack(self, candidates, remain, start, comb, res):
if remain < 0:
return
if remain == 0:
res.append(list(comb))
for i in range(start, len(candidates)):
comb.append(candidates[i])
self.backtrack(candidates, remain - candidates[i], i, comb, res)
comb.pop()
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
"""
时间复杂度:O(sum(len(res)))
空间复杂度:O(target)
"""
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
def dfs(target, start, path):
if target == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
residue = target - candidates[i]
if residue < 0:
break
path.append(candidates[i])
dfs(residue, i, path)
path.pop()
dfs(target, 0, [])
return result
function combinationSum(candidates: number[], target: number): number[][] {
const ans: number[][] = [];
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;
}
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> tmp;
// 在回溯的方法最后添加一个start_idx参数,保证在循环中不走回头路,这样就能保证答案不重复了
// 不再需要额外使用排序和set来去重,更方便
backTrace(candidates, target, tmp, res, 0, 0);
return res;
}
private:
void backTrace(vector<int>& candidates, int target, vector<int>& tmp, vector<vector<int>>& res, int sum, int start_idx)
{
if (sum == target)
{
res.push_back(tmp);
return;
}
if (sum > target)
{
return;
}
int n = candidates.size();
for (int i = start_idx; i < n; ++i)
{
tmp.push_back(candidates[i]);
sum += candidates[i];
backTrace(candidates, target, tmp, res, sum, i);
sum -= candidates[i];
tmp.pop_back();
}
}
};
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;
public List<List
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new LinkedList<>();
backtrack(res, list, candidates, target, 0);
return res;
}
public void backtrack(List<List
if (cur < 0)
return;
if (cur == 0) {
res.add(new LinkedList<>(list));
return;
}
for (int i = pos; i < candidates.length; i++) {
list.add(candidates[i]);
backtrack(res, list, candidates, cur - candidates[i], i);
list.remove(list.size() - 1);
}
}
生成树
class Solution:
def combinationSum(self, candidates, target) :
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
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;
}
private 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:
void solve(int i, vector<int>& candidates, int sum,
vector<int> &ch, int target, vector<vector<int>>& ans) {
if (sum == target) {
ans.push_back(ch);
return;
}
if (i == candidates.size() || sum > target)
return;
solve(i + 1, candidates, sum, ch, target, ans);
ch.push_back(candidates[i]);
solve(i, candidates, sum + candidates[i], ch, target, ans);
ch.pop_back();
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
sort(candidates.begin(), candidates.end());
vector<int> ch;
solve(0, candidates, 0, ch, target, ans);
return ans;
}
};
回溯
function combinationSum(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => -b + a);
const ans: number[][] = [];
dfs(candidates, target, [], (path: number[]) => ans.push(path));
return ans;
}
function dfs(
candidates: number[],
target: number,
path: number[],
output: (path: number[]) => void
) {
if (target === 0) {
output(path);
return;
}
for (const [index, can] of candidates.entries()) {
if (target >= can) {
dfs(
index ? candidates.slice(index) : candidates,
target - can,
[...path, can],
output
);
} else {
return;
}
}
}
39 组合总和
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/combination-sum/
前置知识
题目描述
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