473. Matchsticks to Square
-
DFS, use a sum array to count the sum of each. Make sure you start visite from the big end, because when little number left, they could be composed to a big number, but when big number left, they could not.
-
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
34
35
36
37class {
public boolean makesquare(int[] nums) {
if (nums == null || nums.length < 4) {
return false;
}
int len = 0;
for (int num: nums) {
len += num;
}
if (len % 4 != 0) {
return false;
}
Arrays.sort(nums);
return find(nums, new int[4], nums.length-1, len / 4);
}
private boolean find(int[] nums, int[] sum, int index, int target) {
if (index < 0) {
for (int i = 0; i < 4; i++) {
if (sum[i] != target) {
return false;
}
}
return true;
}
for (int i = 0; i < 4; i++) {
if (sum[i] + nums[index] > target) {
continue;
}
sum[i] += nums[index];
if (find(nums, sum, index-1, target)) {
return true;
}
sum[i] -= nums[index];
}
return false;
}
}
近期评论