leetcode 473. Matchsticks to Square 火柴摆正方形 + 一个经典深度优先遍历DFS的应用

冷不防 2022-06-03 01:43 177阅读 0赞

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:  
Input: \[1,1,2,2,2\]  
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.  
Example 2:  
Input: \[3,3,3,3,4\]  
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.  
Note:  
The length sum of the given matchsticks is in the range of 0 to 10^9.  
The length of the given matchstick array will not exceed 15.

这道题最直接的方法就是DFS深度优先遍历，又涨姿势了，这道题很值得学习

需要注意的是，**这道题需要剪枝，对原数组做排序处理会超时，否者不排序，不作处理不会超时**

还建议和[leetcode 518. Coin Change 2 动态规划DP][leetcode 518. Coin Change 2 _DP]、[leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决][leetcode 279. Perfect Squares _ _ _DP] 、[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]和[leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS][leetcode 416. Partition Equal Subset Sum _DP _ _DFS]一起学习

还有[leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题][leetcode 474. Ones and Zeroes_0_1_DP]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    bool cmp(int a, int b)
    {
        return a >= b;
    }
    
    class Solution
    {
    public:
        bool makesquare(vector<int>& nums) 
        {
            if (nums.size() <= 3)
                return false;
    
            long long sum = 0;
            for (int a : nums)
                sum += a;
            if (sum % 4 != 0)
                return false;
    
            sort(nums.begin(),nums.end(),cmp);
            vector<int> edge(4, 0);
            return dfs(nums, edge, 0, sum / 4);
        }
    
        bool dfs(vector<int>& nums, vector<int>& edge, int index, int target)
        {
            if (index == nums.size())
            {
                for (int i = 0; i < edge.size(); i++)
                {
                    if (edge[i] != target)
                        return false;
                }
                return true;
            }
            else
            {
                for (int i = 0; i < 4; i++)
                {
                    if (edge[i] + nums[index] > target)
                        continue;
                    edge[i] += nums[index];
                    if (dfs(nums, edge, index + 1, target))
                        return true;
                    edge[i] -= nums[index];
                }
                return false;
            }
        }
    };

也可以这么做：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool makesquare(vector<int>& a) 
        {
            int sum = accumulate(a.begin(), a.end(), 0);
            if (a.size() <= 3 || sum % 4 != 0)
                return false;
    
            vector<bool> visit(a.size(), false);
            return dfs(a, visit, sum / 4, 0, 0,4);
        }
    
        bool dfs(vector<int>& a, vector<bool>& visit, int target, int index, int sum,int k)
        {
            if (sum > target)
                return false;
            else if (k == 1)
                return true;
            else if (sum == target)
                return dfs(a, visit, target, 0, 0,k-1);
            else
            {
                for (int i = index; i < a.size(); i++)
                {
                    if (visit[i] == false)
                    {
                        visit[i] = true;
                        if (dfs(a, visit, target, i + 1, sum + a[i], k) == true)
                            return true;
                        visit[i] = false;
                    }
                }
                return false;
            }
        }
    };

[leetcode 518. Coin Change 2 _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 279. Perfect Squares _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78117843
[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 416. Partition Equal Subset Sum _DP _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78752598
[leetcode 474. Ones and Zeroes_0_1_DP]: http://blog.csdn.net/JackZhang_123/article/details/78781584