C++での組み合わせ合計II

候補番号のセット（すべての要素が一意）とターゲット番号があるとします。候補者の数が特定のターゲットに合計される候補者のすべての一意の組み合わせを見つける必要があります。候補者から同じ番号が複数回選ばれることはありません。したがって、要素が[2,3,6,7,8]で、ターゲット値が8の場合、可能な出力は[[2,6]、[8]]

手順を見てみましょう-

• これを再帰的に解決します。再帰関数の名前はsolve（）です。これは、インデックス、配列a、整数b、および別の配列tempを取ります。解決方法は次のように機能します-
• 空の配列解像度を定義する
• b =0の場合、tempをresに挿入し、戻ります
• index =aのサイズの場合、戻ります
• b <0の場合、戻ります
• 配列を並べ替える
• for i in range index to size of a – 1
  • i>インデックスおよびa[i]=a [i – 1]の場合、続行します
  • a[i]を一時的に挿入
  • solve（i + 1、a、b – a [i]、temp）
  • 一時から最後の要素を削除
• index =0、配列a、ターゲットb、および別の配列tempを渡して、solve（）メソッドを呼び出します
• return res

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
  public:
   vector < vector <int> > res;
void solve(int idx, vector <int> &a, int b, vector <int> temp){
      if(b == 0){
         res.push_back(temp);
         return;
      }
      if(idx == a.size())return;
      if(b < 0)return;
      sort(a.begin(), a.end());
      for(int i = idx; i < a.size(); i++){
         if(i > idx && a[i] == a[i-1])continue;
         temp.push_back(a[i]);
         solve(i + 1, a, b - a[i], temp);
         temp.pop_back();
      }
   }
   vector<vector<int> > combinationSum2(vector<int> &a, int b) {
      res.clear();
      vector <int> temp;
      solve(0, a, b, temp);
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,3,6,7,8};
   print_vector(ob.combinationSum2(v, 10)) ;
}

入力

[2,3,6,7,8]
8

出力

[[2, 8, ],[3, 7, ],]