473. 火柴拼正方形

給定很多小短火柴，拼成一個正方形

?

用到的技巧

1.? 排序，傳參數，起到剪枝的效果，排序后前面搜索過的在下層時直接跳過，具體體現為 for (int i = idx;i<n;i++)?

2. 找到正確答案返回true，變為找到不可行的方案之一直接return false；正確答案只有一個，false答案有很多歌；能加快速度。

class Solution { public://改進版搜索回溯 之前的搜索是以找到正確的解為代價 正確的解就一個 很難找 現在反過來 找到錯的直接返回，即在所有剩下的火柴中沒有湊到邊長 直接return falseint n;bool makesquare(vector<int>& nums) {n = nums.size();if(n<4)return false;int sum = accumulate(nums.begin(),nums.end(),0);if(sum%4) return false;int avg = sum/4;sort(nums.rbegin(),nums.rend());vector<bool> visit(n);for(int i = 0;i<4;i++){if(!find(nums,visit,0,avg)) return false;}return true;}bool find(vector<int>& nums,vector<bool>& visit,int idx,int ave){if(ave==0) return true;for (int i = idx;i<n;i++){if(!visit[i]){if(nums[i]<=ave){visit[i] = true;if(find(nums,visit,i+1,ave-nums[i])) return true;visit[i] = false;}} }return false;} };/*//經典dfs 1回溯//對nums排序就相當于剪枝，因為先放大的數 會減小后面分支的數目 比如[2,3,6,4,...],avg=10 放最大的6和4 就會讓快速滿足第一條邊 不然如果前面放3和2 那么在搜索滿足第一條邊的條件時后面會發生很多分支int n;bool makesquare(vector<int>& nums) {n = nums.size();if(n<4)return false;int sum = accumulate(nums.begin(),nums.end(),0);if(sum%4) return false;int avg = sum/4;sort(nums.rbegin(),nums.rend());//不從大到小排序會超時vector<int> edges(4,0);return dfs(nums,edges,0,avg);}bool dfs(vector<int>& nums,vector<int>& edges,int pos,int avg){if(pos==n){return (edges[0]==avg && edges[1]==avg && edges[2]==avg);}for(int i = 0;i<4;i++){if(edges[i]+nums[pos]>avg)continue;edges[i]+=nums[pos];if(dfs(nums,edges,pos+1,avg))return true;edges[i]-=nums[pos];}return false;} }; *//** 2.直接暴力搜索 不優化的話可能超時 class Solution {public boolean makesquare(int[] nums) {if(nums.length ==0 ) return false;int sum =0;for (int i = 0; i < nums.length; i++) {sum+=nums[i];}if(sum/4*4!=sum) return false;return dfs(nums,0,nums.length,0,0,0,0,sum/4);}private boolean dfs(int[] nums, int i, int length, int i1, int i2, int i3, int i4, int i5) {if(i==length){if(i1==i5 && i2==i5 && i3==i5 && i4==i5 ) return true;else return false;}if(i1>i5 || i2>i5 || i3>i5 || i4>i5 ) return false;return dfs(nums,i+1,length,i1+nums[i],i2,i3,i4,i5)||dfs(nums,i+1,length,i1,i2+nums[i],i3,i4,i5)||dfs(nums,i+1,length,i1,i2,i3+nums[i],i4,i5)||dfs(nums,i+1,length,i1,i2,i3,i4+nums[i],i5);} }*/

?

總結

以上是生活随笔為你收集整理的经典回溯之火柴拼正方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。