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

1から9までの数しか使用できないとすると、合計で数nになるk個の可能なすべての組み合わせを生成する必要があると考えてください。各組み合わせは、一意の番号のセットである必要があります。すべての数値は正である必要があり、ソリューションに重複する組み合わせが含まれていてはなりません。したがって、k=3およびn=9の場合、可能な組み合わせは[[1,2,6]、[1,3,5]、[2,3,4]]

これを解決するには、次の手順に従います-

• solveというメソッドを作成してこれを解決するとします。これは再帰的な方法であり、k、n、一時配列を取り、開始します。開始は最初は1です
• n=0の場合
  • tempのサイズ=kの場合、tempをresに挿入して返します
  • for i：=最小値9およびn
    から開始
    • iを一時的に挿入
    • solve（k、n – i、temp、i + 1）
    • tempから最後の要素を削除します
• 主な方法は次のようになります
• tempという空白のベクトルを1つ作成します
• solve（k、n、temp）
• return res

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

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > 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 k, int n, vector <int> temp, int start = 1){
      if(n == 0){
         if(temp.size() == k){
            res.push_back(temp);
         }
         return;
      }
      for(int i = start ; i <= min(9, n); i++){
         temp.push_back(i);
         solve(k, n - i, temp, i + 1);
         temp.pop_back();
      }
   }
   vector<vector<int>> combinationSum3(int k, int n) {
      res.clear();
      vector <int> temp;
      solve(k, n, temp);
      return res;
   }
};
main(){
   Solution ob;
   print_vector(ob.combinationSum3(2, 9));
}

入力

3
9

出力

[[1, 8, ],[2, 7, ],[3, 6, ],[4, 5, ],]