题目描述

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:

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.

题意：给n根火柴，判断能否组成一个正方形。

算法1

(搜索+剪枝)

题解1:DFS搜索+剪枝。DFS函数参数:k已经拼好了几根火柴，cur当前在拼的这根火柴已经拼了多长了，state，因为最多只有15根火柴，所以将其状态用二进制来表示，火柴数组以及数组长度。

搜索策略：如果k = 4，返回true；如果cur=target说明找到了一根新的火柴；否则：遍历所有可拼接的火柴（未被使用过并且拼上去之后不会大于目标长度的火柴）。

剪枝策略：

• 总长度是否是4的倍数，火柴个数是否小于4。
• 将火柴从大到小排序，进行搜索。
• 如果在cur=0的时候就失败了，直接返回false，说明还没有使用的最长的火柴找不到可匹配的组合。
• 如果cur + nums[i] = target的时候匹配失败，直接返回false，这是因为我们已经将火柴降序排列，那么后序搜索的火柴和当前cur的和要小于target。

第三、四剪枝方法可以让程序从100+ms，变成0-4ms。

C++ 代码

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        int n = nums.size(),sum = 0;
        for(int i = 0 ; i < n ; i ++)
            sum += nums[i];
        if(n < 4 || sum % 4 != 0) return false;
        sort(nums.begin(),nums.end(),greater<int>());
        return dfs(0,0,0,sum / 4,nums,n);
    }
    bool dfs(int k,int cur,int state,int target,vector<int>& nums,int n)
    {
        if(k == 4) return true;
        if(cur == target)
            return dfs(k + 1,0,state,target,nums,n);
        for(int i = 0 ; i < n ; i ++)
        {
            if(cur + nums[i] > target)
                continue;
            if(((state >> i) & 1) == 0)
            {
                state = state | (1 << i);
                if(dfs(k,cur + nums[i],state,target,nums,n))
                    return true;
                state = state & ~(1 << i);
                if(cur == 0) return false;
                if(cur + nums[i] == target) return false;
            }
        }
        return false;
    }
};