題目描述

題目來(lái)源

還記得童話《賣火柴的小女孩》嗎？現(xiàn)在，你知道小女孩有多少根火柴，請(qǐng)找出一種能使用所有火柴拼成一個(gè)正方形的方法。不能折斷火柴，可以把火柴連接起來(lái)，并且每根火柴都要用到。

輸入為小女孩擁有火柴的數(shù)目，每根火柴用其長(zhǎng)度表示。輸出即為是否能用所有的火柴拼成正方形。

示例 1:

輸入: [1,1,2,2,2]
輸出: true

解釋: 能拼成一個(gè)邊長(zhǎng)為2的正方形，每邊兩根火柴。
示例 2:

輸入: [3,3,3,3,4]
輸出: false

解釋: 不能用所有火柴拼成一個(gè)正方形。
注意:

給定的火柴長(zhǎng)度和在 0 到 10^9之間。
火柴數(shù)組的長(zhǎng)度不超過(guò)15。

解題思路

• 對(duì)于給定的若干根火柴，我們需要將他們分為四組
• 每一組火柴的長(zhǎng)度之和相同，等于所有火柴長(zhǎng)度之和的四分之一

流程：

使用深度優(yōu)先搜索，枚舉出所有的分組情況，并對(duì)每一種情況，進(jìn)行判斷是否符合上面的情況。

我們對(duì)每一根火柴進(jìn)行搜索，當(dāng)搜索到第i根火柴的時(shí)候，將其放到4組中的一組，對(duì)于放置的每一種方法，繼續(xù)對(duì)i+1根火柴進(jìn)行遞歸搜索。當(dāng)搜索完全部的火柴之后，判斷每組的長(zhǎng)度之和是否相同。

在進(jìn)行搜索之前，我們可以將火柴的長(zhǎng)度從大到小進(jìn)行排序，方便我們先搜索較長(zhǎng)的火柴。這樣做的目的是對(duì)搜索進(jìn)行剪枝，例如當(dāng)火柴的長(zhǎng)度為 [4,4,4,8]時(shí)，，排序后數(shù)組為[8,4,4,4]每條邊的長(zhǎng)度為 5，如果我們先搜索長(zhǎng)度為 8 的火柴，就可以發(fā)現(xiàn)它無(wú)法被放在任意一組中，因此直接退出搜索返回 False。

在leetcode上面 不對(duì)數(shù)組進(jìn)行排序可能會(huì)超時(shí)

代碼實(shí)現(xiàn)

public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums.length < 4) return false;
        int sum = 0;
        for (int i = 0; i < nums.length; i++){
            sum+= nums[i];
        }
        if (sum%4 != 0) return false;
        Integer[] newNums = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++){
            newNums[i] = nums[i];
        }

        Arrays.sort(newNums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int[] bucket = new int[4];
        return dfs(0, newNums, bucket, sum / 4);
    }

    private boolean dfs(int index, Integer[] nums, int[] bucket, int target){
        if (index >= nums.length){
            return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target;
        }

        for (int i = 0; i<4; i++){
            if (bucket[i] + nums[index] > target){
                continue;
            }
            bucket[i] += nums[index];
            if (dfs(index + 1, nums, bucket, target)){
                return true;
            }
            bucket[i] -= nums[index];
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().makesquare(new int[]{1,2,3,4,9,6,5,2}));
        System.out.println(new Solution().makesquare(new int[]{1,1,2,2,2,1,1,1,1}));
    }
}