C++のSquareへのマッチ棒

小さなマッチガールがいるとしましょう。そして、私たちは小さなマッチガールが持っているマッチ棒を正確に知っています。それらのマッチ棒をすべて使い切って1つの正方形を作る方法を見つけなければなりません。スティックを壊してはいけませんが、それらをリンクすることはできます。各マッチスティックは1回だけ使用する必要があります。入力は、女の子が持っているいくつかのマッチ棒で、棒の長さで表されます。マッチガールが持っているすべてのマッチ棒を使用して1つの正方形を作成できるかどうかを表すために、出力はtrueまたはfalseのいずれかになります。したがって、入力が[1,1,2,2,2]のような場合、答えは真になります。長さ2の正方形を作成できるため、片側に長さ1のスティックが2本あります。

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

• solve（）と呼ばれる再帰メソッドを定義します。これは、インデックス、合計配列、ターゲット、およびnums配列を取ります。したがって、これは次のように機能します-
• index> =nums sizeの場合、
  • sums [0]、sum [1]、sum[2]がすべてtargerと同じ場合はtrueを返します
• 0から3の範囲のiの場合-
  • sums [i] + nums [index]>ターゲットの場合、ループの次の部分をスキップします
  • sums [i]：=sums [i] + nums [index]
  • solve（index + 1、sums、target、nums）がtrueの場合、trueを返します
  • sums [i]：=sums [i] – nums [index]
• falseを返す
• メインの方法から、次の手順を実行します-
• numsに要素がない場合は、falseを返します
• x：=0
• 範囲0からnumsのサイズのiの場合、xをnums [j]
増やします。
• xが4で割り切れる場合は、falseを返します
• nums配列を並べ替える
• サイズ4の配列の合計を作成します
• returnsolve（0、sum、x / 4、nums）

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
      if(idx >= nums.size()){
         return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
      }
      for(int i = 0; i < 4; i++){
         if(sums[i] + nums[idx] > target)continue;
         sums[i] += nums[idx];
         if(solve(idx + 1, sums, target, nums)) return true;
         sums[i] -= nums[idx];
      }
      return false;
   }
   bool makesquare(vector<int>& nums) {
      if(nums.size() == 0) return false;
      int x = 0;
      for(int i = 0; i < nums.size(); i++){
         x += nums[i];
      }
      if(x % 4) return false;
      sort(nums.rbegin(), nums.rend());
      vector <int> sum(4);
      return solve(0, sum,x / 4, nums);
   }
};
main(){
   vector<int> v = {1,1,2,2,2};
   Solution ob;
   cout << (ob.makesquare(v));
}

入力

[1,1,2,2,2]

出力

1