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:

1
2
3
4
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:

1
2
3
4
Input: [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

  1. The length sum of the given matchsticks is in the range of 0 to 10^9.
  2. The length of the given matchstick array will not exceed 15.

思路

利用深度优先搜索可以解决这道题。

正方形的四边长都是一样的。如果数组里的所有元素之和不能被4整除，则不能被拼成一个正方形。如果可以被四整除，我们可以一步步往下搜索，直到找到一个可行的拼法。

我们在做DFS的时候，需要一条边一条边进行搜索。edge_size是待寻找的边的长度，找到一条边，edge_count-1。cur_edge是当前找到的所有边长度的总和。

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
class Solution {
private:
    bool flag = false;
public:
    void findedge(vector<int>& nums, int edge_size, int edge_count, int cur_edge){
        if(flag == true) return;
        if(edge_count == 4){
            if (nums.size() == 0) flag = true;
            else return;
        }
        else{
            for(int i = 0; i < nums.size(); i++){
                if(nums[i] < edge_size - cur_edge){
                    vector<int> new_nums(nums);
                    new_nums.erase(new_nums.begin() + i);
                    findedge(new_nums, edge_size, edge_count, nums[i]+cur_edge);
                }
                else if(nums[i] == edge_size - cur_edge){
                    vector<int> new_nums(nums);
                    new_nums.erase(new_nums.begin() + i);
                    findedge(new_nums, edge_size, edge_count+1, 0);
                }
                else return;
            }
        }
    }
    bool makesquare(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        if(sum % 4 != 0){
            return false;
        }
        else{
            //cout << sum / 4;
            findedge(nums, sum/4, 0, 0);
            return flag;
        }
    }
};