473 Matchsticks to Square

473. Matchsticks to Square

1. Question

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 of0to10^9.

2. The length of the given matchstick array will not exceed15.

2. Implementation

(1) Backtracking

思路:

• 计算nums数组的总和，如果总和不是4的倍数，显然无法通过nums总成4条正方形的边长

• 对于正方形的4条边，我们利用backtracking的方法检查是否每条边都能通过nums构成目标长度 (nums数组每个数的总和除以4,即sum / 4), 对于nums中被用过的数，我们将nums[i] 标记为 -1, 注意在回溯过程中，如果一条边能通过nums构成目标长度，则nums里标记为-1的数不会还原成原来的数，这样可以避免同一个数被不同边重复利用

• 为了提高算法速度，我们在回溯之前首先把nums先排序，然后回溯时我们都从后往前处理数字的元素，这样的好处是我们可以迅速发现大于正方形目标长度的元素，提前跳出递归

class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

        // 边长总和不是4的倍数，不可能组成正方形
        if (sum % 4 != 0) {
            return false;
        }

        // 排序nums，然后从后往前处理，好处是可以在之后的递归中可以迅速跳过无法构成square length的元素
        Arrays.sort(nums);
        int[] squareLen = new int[4];

        // 检查4条边是否都能通过nums构成正方形的边长
        for (int i = 0; i < 4; i++) {
            if (!checkOneLine(nums, nums.length - 1, sum / 4)) {
                return false;
            }
        }
        return true;
    }

    public boolean checkOneLine(int[] nums, int index, int len) {
        // target长度变成0，说明当前的边长可以通过nums构成target长度
        if (len == 0) return true;

        // 减枝
        if (len < 0 || index < 0) return false;

        for (int i = index; i >= 0; i--) {
            if (nums[i] == -1) continue;

            int curLen = nums[i];
            // 将用过的nums元素标记为-1
            nums[i] = -1;
            if (checkOneLine(nums, i - 1, len - curLen)) {
                return true;
            }
            // 回溯会员
            nums[i] = curLen;
        }
        return false;
    }
}

3. Time & Space Complexity

Backtracking: 时间复杂度O(n!) 解析, 空间复杂度O(n)