1、題目

火柴拼正方形 - 力扣（LeetCode） https://leetcode-cn.com/problems/matchsticks-to-square/

2、題解

首先我們可以對所有火柴進行求和，如果sum不能整除4，說明無論如何都無法拼湊出正方形。然后我們嘗試將火柴分配到四個邊長，如果最后四邊都相等，則說明可以拼湊。

3、代碼

class Solution {
        public boolean makesquare(int[] nums) {
            if (nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 4 != 0) {
                return false;
            }
            int target = sum / 4;
            return ResultForDPS(nums, 0, target, target, target, target);

        }

        private boolean ResultForDPS(int[] nums, int index, int one, int two, int three, int four) {
            if(index==nums.length){
                return one==two&&two==three&&three==four;
            }
            if(one<0||two<0||three<0||four<0){
               return false;
            }
            return ResultForDPS(nums,index+1,one-nums[index],two,three,four)||
                    ResultForDPS(nums,index+1,one,two-nums[index],three,four)||
                    ResultForDPS(nums,index+1,one,two,three-nums[index],four)||
                    ResultForDPS(nums,index+1,one,two,three,four-nums[index]);
        }
    }

4、執(zhí)行結果

image.png