假设有一个火柴的小女孩。而且我们确切知道小火柴的女孩有哪些火柴棍，我们必须找到一种方法来耗尽所有这些火柴棍来制作一个正方形。我们不应该破坏任何一根火柴，但可以将它们连接起来，并且每根火柴必须精确使用一次。我们输入的将是女孩拥有的多个火柴，并以其火柴长度表示。我们的输出将为true或false，以表示我们是否可以使用火柴女孩所拥有的所有火柴来制作一个正方形。因此，如果输入像[1,1,2,2,2]，则答案将是正确的，因为我们可以制作一个长度为2的正方形，一侧将有两个长度为1的木棍。
为了解决这个问题，我们将遵循以下步骤-
定义一个称为的递归方法solve()。这将使用索引，sums数组，target和nums数组。所以这将如下工作-
如果索引> = nums大小，则
当sums [0]，sum [1]和sum [2]全部与targer相同时，返回true
对于i在0到3范围内-
如果sums [i] + nums [index]> target，则跳过循环的下一部分
sums [i]：= sums [i] + nums [index]
如果solve（index + 1，sums，target，nums）为true，则返回true
sums [i]：= sums [i] – nums [index]
返回假
从主要方法中，执行以下操作-
如果nums没有元素，则返回false
x：= 0
对于范围从0到nums的i，将x增加nums [j]
如果x可被4整除，则返回false
排序nums数组
制作大小为4的数组总和
返回solve（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