組合總和Leetcode解決方案


難度級別
經常問 土磚 Airbnb的 亞馬遜 蘋果 Atlassian的 彭博社 ByteDance 易趣 Facebook 高盛 谷歌 LinkedIn Microsoft微軟 神諭 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是所有其他候選項中的最小值。