Leetcode 39. Combination Sum
- 题目
- 解析:
题目
解析:
这题是77的follow up。只需要做很小的改动就可以了如下:
- 77因为不可以用重复数字,所以在recursion的时候传的参数是i + 1,而这边每个数字可以被重复用,所以传i
- 在recursion开始的时候判断当前组合是不是符合要求
python代码如下:
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def back_tracking(curr,first):if sum(curr) == target:ans.append(curr[:])returnif sum(curr) > target:returnfor i in range(first,len(candidates)):curr.append(candidates[i])back_tracking(curr,i)//i here but i+1 in 77curr.pop()ans = []back_tracking([],0)return ans
C++版本如下:
由于c++里没有提供求和的库函数,所以需要单独变量保存current sum
class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;vector<int> curr;back_tracking(0,curr,0,target,ans,candidates);return ans;}void back_tracking(int first,vector<int> curr,int currsum,int target,vector<vector<int>>& ans,vector<int>& candidates){
if (currsum==target){
ans.push_back(curr);return;}if (currsum>target) return;for (int i=first;i<candidates.size();++i){
curr.push_back(candidates[i]);back_tracking(i,curr,currsum+candidates[i],target,ans,candidates);curr.pop_back();}}
};