C++でマッチ棒をすべて使って正方形を作れるか判定するアルゴリズム

ここにマッチ売りの少女がいると想像してください。彼女が持っているマッチ棒の本数と長さは正確にわかっており、そのすべてのマッチ棒を使い切って1つの正方形を作れるかどうかを調べる必要があります。

条件は以下のとおりです。

• マッチ棒を折ったり切ったりしてはいけない
• 棒同士をつなぎ合わせることは可能
• 各マッチ棒は必ずちょうど1回使用する

入力は少女が持っているマッチ棒の長さのリストで、出力は正方形を作成できる場合は true、できない場合は false となります。

たとえば入力が [1,1,2,2,2] の場合、答えは true です。一辺の長さが2の正方形を作ることができ、一辺には長さ1のマッチ棒を2本組み合わせればよいからです。

解法のアプローチ(バックトラッキング)

この問題は、深さ優先探索(DFS)+ バックトラッキングを用いて効率的に解くことができます。全体の長さを4で割った値が一辺の目標長となり、各マッチ棒を4つの辺のいずれかに割り振っていきます。

再帰関数 solve() の設計

まず、index・sums配列・target・nums配列を引数にとる再帰メソッド solve() を定義します。処理の流れは次のとおりです。

1. 終了条件: index が nums のサイズ以上になったら、sums[0]、sums[1]、sums[2] がすべて target と等しい場合に true を返す(sum[3] は自動的に target と一致するため、3つの確認で十分です)。
2. i を 0 から 3 までループする:
   • sums[i] + nums[index] > target の場合は、その辺に収まらないためスキップする
   • sums[i] += nums[index](現在のマッチ棒を i 番目の辺に追加)
   • solve(index + 1, sums, target, nums) が true を返せば、そのまま true を返す
   • そうでなければ sums[i] -= nums[index](バックトラックして元に戻す)
3. どの辺にも配置できなければ false を返す。

メイン関数での事前チェック

呼び出し元では、以下の前処理を行います。

1. nums が空の場合は false を返す
2. 全マッチ棒の合計長 x を計算する
3. x が 4 で割り切れない場合は、正方形を作れないので false を返す
4. nums を降順にソートする(長い棒から先に配置することで、枝刈りの効率が大幅に向上します)
5. サイズ4の sums 配列を用意する
6. solve(0, sum, x / 4, nums) の結果を返す

C++実装例

#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

まとめ

このアルゴリズムのポイントは、次の3点です。

• 早期リターン: 合計が4で割り切れない時点で即座に false を返し、無駄な探索を回避
• 降順ソートによる枝刈り: 長い棒を先に配置することで、失敗パターンを早い段階で検出できる
• バックトラッキング: 配置に失敗したら状態を元に戻し、別の辺を試行する

これにより、すべてのマッチ棒を無駄なく使い切って正方形が構成できるかどうかを正確に判定できます。