コンビネーションサムリートコードソリューション


難易度 ミディアム
よく聞かれる Adobe のAirbnb Amazon (アマゾン) Apple アトラシアン ブルームバーグ ByteDance オークション Facebook ゴールドマン·サックス Google LinkedIn マイクロソフト オラクル Snapchat 正方形である ユーバー ヴイエムウェア ウォルマート・ラボ
配列 バックトラッキング

問題のCombinationSum Leetcode Solutionは、 配列 または整数とターゲットのリスト。 これらの整数を使用して、指定されたターゲットに達する回数を何度でも使用できる組み合わせを見つけるように指示されています。 つまり、より正式には、指定された整数を何度でも使用して、指定されたターゲットに追加することができます。 必要な出力は、合計が指定されたターゲットに等しい組み合わせです。

コンビネーションサムリートコードソリューション

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が繰り返されます。 XNUMXつの出力すべてが指定されたターゲットに合計されることを確認できます。

組み合わせ合計リートコードソリューションのアプローチ

問題へのアプローチは簡単に見つかります。 一般に、このような問題では、バックトラッキングを使用する必要があります。 そのような質問では、完全な検索を行って答えを見つける必要があるためです。 したがって、最初に、与えられた整数のリストをソートします。 その後、整数の現在の一時リストに整数を追加し続け、指定されたターゲットに合計するために必要な残りの合計を追跡する再帰関数を作成します。 したがって、再帰関数内では、XNUMXつの基本ケースを保持します。 最初の基本ケースは、必要な残りの合計が負になるかどうかを確認することです。 その場合、再帰関数から戻ります。 XNUMX番目の基本ケースは、残りの合計がゼロに等しい場合に必要な条件です。 残りの合計がゼロの場合、これは必要な目標に到達したことを意味します。 その時点で、整数の現在の一時リストを配列の出力配列にプッシュします。

コード

組み合わせ合計リートコードソリューションの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

コンビネーションサムリートコードソリューションの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は他のすべての候補の中で最小の要素です。