DFS-Recall10

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/matchsticks-to-square/]

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

1
2
3
4
输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

1
2
3
4
输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

注意:

  1. 给定的火柴长度和在 0 到 10^9之间。
  2. 火柴数组的长度不超过15。

算法描述

这一题首先是判断数组和是不是4的倍数，如果不是的话，那一定不能拼成正方形。

然后，遍历一遍数组，若有一个数大于数组和/4，那么也一定不能拼成正方形。

接着就要用回溯来判断了，这题的回溯指的是，把火柴放进不同的边里去。

因此相当于，对于任意一根火柴，将火柴放入大小为4的数组某一维度中去。

直到全部的火柴处理完，在处理过程中，如果某一个边的大小已经超过数组和/4，那就

剪枝，因为这样是不可能组成正方形的。

这里的贪心在于，如果从大到小处理，那么速度将会快的很多。因此在回溯之前，先给数组排序。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if(nums.size()<4)return false;
        int sum =0;
        for(int i=0;i<nums.size();i++)sum+=nums[i];
        if(sum%4)return false;
        sort(nums.rbegin(),nums.rend());
        int bucket[4] = {0};
        return dfs(0,nums,sum/4,bucket);
    }
    
    bool dfs(int i,vector<int> &nums,int t,int b[]){
        if(i>=nums.size()){
            return b[0]==t&&b[1]==t&&b[2]==t&&b[3]==t;
        }
        for(int j=0;j<4;j++){
            if(b[j]+nums[i]>t)continue;
            b[j]+=nums[i];
            if(dfs(i+1,nums,t,b))return true;
            b[j]-=nums[i];
        }
        return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    boolean ans = false;
    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;
        Arrays.sort(nums);
        dfs(nums.length-1,nums,target,new int[4]);
        return ans;
    }
    
    public void dfs(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)
                dfs(cur-1,nums,target,temp);
            temp[i] = last;
        }
    }
}