leetcode473 火柴拼正方形

難度 - 中等
原題鏈接 - leetcode473 火柴拼正方形

題目描述

你將得到一個整數數組 matchsticks ，其中 matchsticks[i] 是第 i 個火柴棒的長度。你要用 所有的火柴棍 拼成一個正方形。你 不能折斷 任何一根火柴棒，但你可以把它們連在一起，而且每根火柴棒必須 使用一次 。
如果你能使這個正方形，則返回 true ，否則返回 false 。

示例1：
輸入: matchsticks = [1,1,2,2,2]
輸出: true
解釋: 能拼成一個邊長為2的正方形，每邊兩根火柴。

示例 2:
輸入: matchsticks = [3,3,3,3,4]
輸出: false
解釋: 不能用所有火柴拼成一個正方形。

提示:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 1e8

回溯算法

這個題的意思可以轉換為，將數組分為四個相等的數組。
用回溯算法，進行選擇。先看下回溯算法的基本流程。

廢話不多說，直接上回溯算法框架，解決一個回溯問題，實際上就是一個決策樹的遍歷過程，站在回溯樹的一個節點上，你只需要思考 3 個問題：
1.路徑：也就是已經做出的選擇。
2.選擇列表：也就是你當前可以做的選擇。
3.結束條件：也就是到達決策樹底層，無法再做選擇的條件。

代碼框架

result = []
def backtrack(路徑, 選擇列表):if 滿足結束條件:result.add(路徑)returnfor 選擇 in 選擇列表:做選擇backtrack(路徑, 選擇列表)撤銷選擇

代碼：

  int n ,t;int[]_nums;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;}Arrays.sort(nums);_nums = nums;n = nums.length;t = sum / 4;return dfs(n - 1,0,0,new boolean[n]);}/**** @param index* @param cur 當前元素和* @param cnt 已經湊夠幾個和為t的集合。* @param vis 標記哪些元素被使用過了。* @return*/boolean dfs(int index,int cur,int cnt,boolean[]vis){if (cnt == 4){return true;}if (cur == t){return dfs(n - 1,0,cnt + 1,vis);}for (int i = index;i >= 0;i--){if (vis[i] || cur + _nums[i] > t){continue;}vis[i] = true;if (dfs(i - 1,cur + _nums[i],cnt,vis)){return true;}vis[i] = false;if (cur == 0){return false;}}return false;}

上期經典算法

leetcode292. Nim 游戲