组合总和Leetcode解决方案


难度级别 中等
经常问 土砖 Airbnb的 亚马逊 Apple Atlassian的 彭博 ByteDance 易趣 Facebook 高盛 谷歌 LinkedIn 微软 神谕 Snapchat 广场 尤伯杯 VMware的 沃尔玛实验室
排列 回溯

组合总和Leetcode解决方案为我们提供了一个问题 排列 或整数列表和目标。 我们被告知要找到可以使用这些整数任意次数的组合,这些组合加总到给定的目标。 因此,更正式地说,我们可以使用给定整数任意次,以便它们添加到给定目标中。 所需的输出是总和等于给定目标的组合。

使用案列组合总和Leetcode解决方案

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

说明:给定的输出总计到给定的目标。 即使我们尝试提出任何其他组合。 我们将最终以不同的顺序排列相同的整数。 但是顺序并不重要,只有组合才有意义。

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

说明:由于我们可以多次使用同一整数。 在输出中,我们在第一个输出中使用了2次。 类似地,在第二输出中重复2。 我们可以验证所有3个输出的总和是否达到给定的目标。

组合和Leetcode解决方案的方法

解决问题的方法很容易找到。 通常,在诸如此类的问题中,我们需要使用回溯。 因为在这样的问题中,我们需要进行完整的搜索并找到答案。 因此,首先,我们对提供给我们的整数列表进行排序。 然后,我们创建一个递归函数,该函数继续将一个整数添加到当前的临时整数列表中,并跟踪累加到给定目标所需的剩余总和。 因此,在递归函数内部,我们保留两个基本案例。 第一个基本情况是检查所需的剩余金额是否为负。 在这种情况下,我们将从递归函数中返回。 如果剩余总和为零,则第二个基本情况是我们的必要条件。 如果剩余总和为零,则表示我们已达到所需的目标。 在这一点上,我们将当前的临时整数列表推入数组的输出数组。

代码

组合总和Leetcode解决方案的C ++代码

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

组合总和Leetcode解决方案的Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

复杂度分析

时间复杂度

O(N ^(M / T +1)) 其中N是候选项数,M是所有给定整数中最小的候选项,T是目标值。 因此,时间复杂度是指数级的,这是可以预期的,因为该算法是递归的回溯。

空间复杂度

O(T / M), 其中T是目标值,M是所有其他候选项中的最小值。