当前位置: 代码迷 >> 综合 >> Leetcode 39. Combination Sum(python+cpp)
  详细解决方案

Leetcode 39. Combination Sum(python+cpp)

热度:20   发布时间:2023-11-26 07:37:46.0

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();}}
};
  相关解决方案