C++刷LeetCode（473. 火柴拼正方形）【回溯*】【剪枝】

糖逗

题目描述：

1. 还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
   
2. 
   
3. 输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: [1,1,2,2,2]
   
8. 输出: true
   
9. 
   
10. 解释: 能拼成一个边长为2的正方形，每边两根火柴。
    
11. 示例 2:
    
12. 
    
13. 输入: [3,3,3,3,4]
    
14. 输出: false
    
15. 
    
16. 解释: 不能用所有火柴拼成一个正方形。
    
17. 注意:
    
18. 
    
19. 给定的火柴长度和在 0 到 10^9之间。
    
20. 火柴数组的长度不超过15。
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/matchsticks-to-square
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.    
   
4.     vector<bool>st;
   
5.     bool makesquare(vector<int>& nums) {
   
6.         int sum = 0;
   
7.         for(auto u : nums) sum += u;
   
8.         if(sum % 4 != 0) return false;
   
9.         sort(nums.rbegin(),nums.rend());
   
10.         st = vector<bool>(nums.size());
    
11.         return dfs(nums,0,0,sum / 4);
    
12.     }
    
13. 
    
14.     bool dfs(vector<int>&nums,int u , int cur, int length)
    
15.     {
    
16.         if(cur == length) u++, cur = 0;
    
17.         if(u == 4)return true;
    
18.         for(int i = 0; i < nums.size(); i++)
    
19.         {
    
20.             if(!st[i] && cur + nums[i] <= length)
    
21.             {
    
22.                 st[i] = true;
    
23.                 if(dfs(nums,u , cur + nums[i], length))return true;
    
24.                 st[i] = false;
    
25.                 if(cur == 0)return false;//如果cur = 0 ,第一个失败了，直接剪掉
    
26.                 if(cur + nums[i] == length) return false;//虽然等于length但是没有达到u==4或没有用完全部数据
    
27.                 while(i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;//当前失败，跳过相同大小木棒
    
28. 
    
29.             }
    
30.         }
    
31.         return false;
    
32.     }
    
33. };

复制代码

参考链接：https://leetcode-cn.com/problems ... n-by-cuiwanxin1998/

糖逗

有思路和想法，但是没写出来

糖逗

之后再做一遍