473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

1
2
输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

1
2
输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

注意:

给定的火柴长度和在 0 到 10^9之间。火柴数组的长度不超过15。

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
class Solution {
public:
    int part;
    vector<bool> vis;
    bool f = true;
    bool makesquare(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];
        if(!sum || sum%4) return false;
        part = sum / 4;
        vis = vector<bool>(nums.size());
        //从大到小枚举所有边
        sort(nums.begin(),nums.end(),greater<int>());
        return dfs(nums,0,0,part);
    }
    //u:当前选了几个数，sum：当前的和，k:选到了第几层
    bool dfs(vector<int> &nums,int u,int cur,int length){
        if(cur == length) u+=1,cur=0;
        if(u == 4) return true;
        for(int i = 0; i < nums.size(); i++){
            //
            if(!vis[i] && cur+nums[i] <= length){
                vis[i] = true;
                if(dfs(nums,u,cur+nums[i],length)) return true;
                vis[i] = false;
                //如果当前木棒拼接失败，并且是第一个，则剪掉。
                if(cur == 0) return false;
                //如果当前木棒拼接失败，并且是最后一个，则剪掉。
                if(cur + nums[i] == length) return false;
                //如果当前木棒拼接失败，跳过所有相同长度的木棒。
                while(i+1 < nums.size() && nums[i] == nums[i+1]) i++;
                
            }
        }
        return false;
    }
};

思路：

剪枝策略：

  • 从小到大枚举所有边
  • 每条边内部的木棒长度规定为从大到小
  • 如果当前木棒拼接失败，则跳过接下来所有长度相同的木棒。
  • 如果当前木棒拼接失败，且是当前边的第一个，则直接剪掉当前分支。
  • 如果当前木棒拼接失败，且是当前边的最后一个，则直接剪掉当前分支。