1.LeetCode473題目鏈接

https://leetcode-cn.com/problems/matchsticks-to-square/submissions/

2.解題思路

首先我們將不能組成正方形的結(jié)果去除，邊長不能整除4的，然后記錄正方形變長，遞歸累加到每個(gè)邊等于變長，若可以得到四條邊則為true。

 public boolean makesquare(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum == 0 || sum % 4 != 0) {
            return false;
        }
        int target = sum / 4;
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }
        //群里同學(xué)說現(xiàn)排序效率更高，試了下，提高了40%的效率。。
        Arrays.sort(nums);
        search(nums.length - 1, nums, target, new int[4]);
        return ans;

    }

    boolean ans = false;

    void search(int cur, int[] nums, int target, int[] temp) {
        if (ans){
            return;
        }
        if (cur == -1) {
            for (int num : temp) {
                if (num != target)
                    return;
            }
            ans = true;
            return;
        }
        for (int i = 0; i < temp.length; i++) {
            int last = temp[i];
            temp[i] += nums[cur];
            if (temp[i] <= target) {
                search(cur - 1, nums, target, temp);
            }
            temp[i] = last;
        }
    }

image