leetcode473. 火柴拼正方形

1.题目描述：

你将得到一个整数数组matchsticks，其中matchsticks[i]是第i个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次。如果你能使这个正方形，则返回true，否则返回false。

2.回溯：与leetcode698. 划分为k个相等的子集做法一致，把k改为4即可。

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int i = 0; i < matchsticks.length; i++)  sum += matchsticks[i];
        if (sum % 4 != 0) return false;
        int target = sum / 4;
        Arrays.sort(matchsticks);
        if (matchsticks[matchsticks.length - 1] > target) return false;
        boolean[] flag = new boolean[matchsticks.length];
        return backTracking(matchsticks, matchsticks.length - 1, target, 4, 0, flag);
    }
    
    public boolean backTracking(int[] matchsticks, int index, int target, int count, int curSum, boolean[] flag) {
        if (count == 1) return true;
        if (curSum == target) return backTracking(matchsticks, matchsticks.length - 1, target, count - 1, 0, flag);
        for (int i = index; i >= 0; i--) {
            if (flag[i] || curSum + matchsticks[i] > target) continue;
            flag[i] = true;
            if (backTracking(matchsticks, i - 1, target, count, curSum + matchsticks[i], flag)) return true;
            flag[i] = false;
            while (i > 0 && matchsticks[i] == matchsticks[i - 1]) i--; 
        }
        return false;
    }
}