Force deduction solution summary 473 match to square

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

You will get an array of integers matchsticks , among matchsticks[i] It's No i  The length of a matchstick . Do you want us to use All the matchsticks   Make a square . you Can't break Any matchstick , But you can connect them together , And every matchstick must Use it once .

If you can make this square , Then return to true , Otherwise return to false .

Example  1:

Input : matchsticks = [1,1,2,2,2]
Output : true
explain : Can be put together into a side length of 2 The square of , Two matches on each side .
Example  2:

Input : matchsticks = [3,3,3,3,4]
Output : false
explain : You can't make a square out of all the matches .
 

Tips :

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/matchsticks-to-square
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  First, add up , Find the average average.
*  Then we start the recursive loop , First, take out from the array 0 The number of positions , Put it in a1 Location .
*  Take it out again 1 The number of positions , There are two possibilities , The first is and a1 Add up , The second is to put a2 Location .
*  Take it out again 2 The number of positions , There are three possibilities , The first is and a1 Add up , The second is and a2 Add up , The third is to put a3 Location .
*  By analogy , If a1,a2,a3,a4 Any number is greater than the average average, The failure . If index The position is equal to -1, Then it proves that there is no problem .
*  Of course , There are two optimizations for the above , The first number sorts the array in advance , This is conducive to faster access false perhaps true The logic of .
*  The second is that we can put a1,a2,a3,a4 Express in an array , Change the value back after use .

Code ：

public class Solution473 {

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int i : matchsticks) {
            sum += i;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int average = sum / 4;
        Arrays.parallelSort(matchsticks);
        return recursion(matchsticks, matchsticks.length - 1, average, 0, 0, 0, 0);
    }

    private boolean recursion(int[] matchsticks, int index, int average, int a1, int a2, int a3, int a4) {
        if (a1 > average || a2 > average || a3 > average || a4 > average) {
            return false;
        }
        if (index == -1) {
            return true;
        }
        int value = matchsticks[index];
        index--;
        if (a1 == 0) {
            return recursion(matchsticks, index, average, value, a2, a3, a4);
        }
        if (a2 == 0) {
            return recursion(matchsticks, index, average, a1 + value, a2, a3, a4) || recursion(matchsticks, index, average, a1, value, a3, a4);
        }
        if (a3 == 0) {
            return recursion(matchsticks, index, average, a1 + value, a2, a3, a4) || recursion(matchsticks, index, average, a1, a2 + value, a3, a4) || recursion(matchsticks, index, average, a1, a2, a3 + value, a4);
        }
        if (a4 == 0) {
            return recursion(matchsticks, index, average, a1 + value, a2, a3, a4) || recursion(matchsticks, index, average, a1, a2 + value, a3, a4) || recursion(matchsticks, index, average, a1, a2, a3 + value, a4) || recursion(matchsticks, index, average, a1, a2, a3, value);
        }
        return recursion(matchsticks, index, average, a1 + value, a2, a3, a4) || recursion(matchsticks, index, average, a1, a2 + value, a3, a4) || recursion(matchsticks, index, average, a1, a2, a3 + value, a4) || recursion(matchsticks, index, average, a1, a2, a3, a4 + value);
    }

}