C++で等しい合計のk個のパーティションでリストをパーティション化できるかどうかをチェックするプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、各サブセットの合計が同じであるk個の異なるサブセットにnumsを分割できるかどうかを確認する必要があります。

したがって、入力がnums =[4、2、6、5、1、6、3] k =3のようである場合、出力はTrueになります。これは、[6、3]、[6]のように分割できるためです。 、2、1]、および[4、5]。

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

• 関数check（）を定義します。これには、配列vが必要です。
• iを初期化する場合：=1、i
• v[i]がv[0]と等しくない場合、-
  • falseを返す

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool check(vector<int>& v) {
      for (int i = 1; i < v.size(); i++) {
         if (v[i] != v[0])
            return false;
      }
      return true;
   }
   bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
      if (idx == nums.size()) {
         return check(temp);
      }
      bool ret = false;
      for (int i = 0; i < temp.size(); i++) {
         temp[i] += nums[idx];
         ret = dfs(idx + 1, nums, temp);
         if (ret)
            return true;
         temp[i] -= nums[idx];
      }
      return false;
   }
   bool solve(vector<int>& nums, int k) {
      vector<int> temp(k);
      return dfs(0, nums, temp);
   }
};
bool solve(vector<int>& nums, int k) {
   return (new Solution())->solve(nums, k);
}
int main(){
   vector<int> v = {4, 2, 6, 5, 1, 6, 3};
   int k = 3;
   cout << solve(v, 3);
}

入力

{4, 2, 6, 5, 1, 6, 3}, 3

出力

1