0473. Matchsticks to Square

---

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [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: matchsticks = [3,3,3,3,4]

Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

• 1 <= matchsticks.length <= 15
• 0 <= matchsticks[i] <= 10^9

---

解法1

暴力求解就好了. 毕竟最多只有15根火柴.

只有一点需要注意, 就是先把原始数组排序, 然后从大到小进行计算, 相较随机顺序的数组可以较快的找到结果(如果结果是true的话. false的话花费的时间是一样的).

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int m : matchsticks)
            sum += m;
        
        // 如果总长度不能被4整除, 返回false
        if(sum % 4 != 0)
            return false;
        
        Arrays.sort(matchsticks);
        
        return helper(new int[4], sum / 4, matchsticks, matchsticks.length - 1);
    }
    
    public boolean helper(int[] borders, int width, int[] ms, int index){
        // 如果顺利的把所有火柴放完,返回true
        if(index < 0)
            return true;
        
        int m = ms[index];
        
        // 4个边都计算
        for(int i = 0; i < 4; i++){
            
            // 只有当不超过边长的时候, 才进行下一次迭代计算
            if(borders[i] + m <= width){
                borders[i] += m; 
                // 如果得到ture, 直接结束结算并返回结果
                if(helper(borders, width, ms, index - 1))
                    return true;
                borders[i] -= m;
            }
        }
        return false;
    }
}