473. Matchsticks to Square

发表于 | 分类于

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

解法1：DFS

首先，如果能摆成正方形，正方形的边长是确定的。也就是所有的数加起来/4。然后就是运行一个DFS。核心思想是，用一个数组代表每一个边长，然后尝试不同的组合，终结条件是每条边长都是target。
这里有一个优化是需要先对所有火柴递减排列：原因是

1
Sorting the input array DESC will make the DFS process run much faster. Reason behind this is we always try to put the next matchstick in the first subset. If there is no solution, trying a longer matchstick first will get to negative conclusion earlier. Following is the updated code. Runtime is improved from more than 1000ms to around 40ms. A big improvement.

也就是说，如果一个组合不能成功拼成正方形的话，先用长的可以更快的得到false的结论，而不用多循环好多次来得到这个结论。这样运行速度就加快了。
C++

1

Java

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int target = sum / 4;   // this is the length of square
        Arrays.sort(nums);  // sort the nums descending
        reverse(nums);
        int[] sides = new int[4];
        return dfs(sides, nums, 0, target);
    }
    private void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
        return;
    }
    private boolean dfs(int[] sides, int[] nums, int pos, int target) {
        if (pos == nums.length) {
            if (sides[0] == target && sides[1] == target && sides[2] == target) {
                return true;
            }
            return false;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + nums[pos] > target) {
                continue;
            }
            sides[i] += nums[pos];
            boolean temp = dfs(sides, nums, pos + 1, target);
            if (temp) {
                return true;
            }
            sides[i] -= nums[pos];
        }
        return false;
    }
}