leetcode473 Matchsticks to Square

时间:2024-09-04 14:37:02

一开始想求所有结果为target的组合来着,但是所选元素不能重叠。用这个递归思想很简单,分成四个桶,每次把元素放在任意一个桶里面,最后如果四个桶相等就可以放进去,有一个地方可以剪枝,假如任意一个桶的元素和大于了target果断return。另一个优化的点在于,如果要求能不能也就是找到一个就可以的话,那么从大到小的找可以减少回溯的次数,否则会超时。学会了一个sort函数从大到小排序的新方法。sort(nums.rbegin(),nums.rend()); leetcode不能用sort(,,cmp)的那种方法不知道为什么。

#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<int>ans;
vector<vector<int>>res;
vector<bool>used;
bool cmp(int a, int b)
{
return a > b;
}
bool permutation(vector<int>nums, int index, int n,int a,int b,int c,int d)
{
if (a>n/||b>n/||c>n/||d>n/)
return false;
if (index==nums.size()&&a==b&&c==d&&b==c)
{
return true;
}
return permutation(nums, index + , n, a + nums[index], b, c, d) || permutation(nums, index + , n, a, b + nums[index], c, d) || permutation(nums, index + , n, a, b, c + nums[index], d) || permutation(nums, index + , n, a, b, c, d + nums[index]);
}
public:
bool makesquare(vector<int>& nums) {
if (nums.size() == )
return false;
int sum=;
int i;
sort(nums.rbegin(),nums.rend());
for (i = ; i < nums.size(); i++)
{
sum += nums[i];
}
if (sum % != ||nums[nums.size()-]>sum/)
return false;
return permutation(nums, , sum,,,,);
}
};