-
Notifications
You must be signed in to change notification settings - Fork 0
/
MatchstickToSquare.cpp
33 lines (31 loc) · 1.37 KB
/
MatchstickToSquare.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Matchsticks to Square
// You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick.
// You want to use all the matchsticks to make one square. You should not break any stick,
// but you can link them up, and each matchstick must be used exactly one time.
// Return true if you can make this square and false otherwise.
class Solution {
public:
bool dfs(vector<int> &nums,int index,int side,int s1,int s2,int s3,int s4)
{
if(index==nums.size())
return s1==side && s2==side && s3==side;
if(s1+nums[index]<=side && dfs(nums,index+1,side,s1+nums[index],s2,s3,s4))
return true;
if(s2+nums[index]<=side && s2!=s1 && dfs(nums,index+1,side,s1,s2+nums[index],s3,s4))
return true;
if(s3+nums[index]<=side && s3!=s2 && s3!=s1 && dfs(nums,index+1,side,s1,s2,s3+nums[index],s4))
return true;
if(s4+nums[index]<=side && s4!=s3 && s4!=s2 && s4!=s1 && dfs(nums,index+1,side,s1,s2,s3,s4+nums[index]))
return true;
return false;
}
bool makesquare(vector<int>& nums) {
int n=nums.size();
if(n<4) return false;
int perimeter=accumulate(nums.begin(),nums.end(),0);
int side=perimeter/4;
if(side*4!=perimeter) return false;
sort(nums.rbegin(),nums.rend());
return dfs(nums,0,side,0,0,0,0);
}
};