# 0473. Matchsticks to Square
###### tags: `Leetcode` `Medium` `Backtracking` `DFS`
Link: https://leetcode.com/problems/matchsticks-to-square/
## 思路
### 思路一 DFS
挨个尝试所有的nums元素的组合,是否能恰好构成四段大小相等的sum(这个sum就是nums总数和的四分之一)
本题设计的递归函数: ```dfs(int[] matchsticks, boolean[] used, int edge, int remain, int curr, int start)```

remain表示我们还有几条边没凑.如果凑满四条边,就说明成功.

curr表示对于当前的边,我们已经累加了多少数字.如果累加到恰好curSum==sum,那么我们就清零开始DFS下一条边.如果curr>sum,就可以终止当前搜索.如果curr<sum,则当前边还需要尝试搜索更多数字加入进去.

used是标记每个数字是否被访问过.因为是整体就是深度搜索+回溯的算法,所以要记得退出时要恢复标记.

另外，一个常用的节省时间的技巧是将nums按照从大到小排序，这样能更容易遇到不合条件的情况，及早剪枝，避免过深的探索。

和[0698. Partition to K Equal Sum Subsets](https://hackmd.io/GIVP1eoSRdaIWt1qFMnDQQ)很像
### 思路二 Memorization & DFS
我还没仔细看
## Code

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int diameter = 0;
        for(int stick:matchsticks) diameter += stick;
        if(diameter%4!=0) return false;
        boolean[] used = new boolean[matchsticks.length];
        Arrays.sort(matchsticks);
        return dfs(matchsticks, used, diameter/4, 4, 0, matchsticks.length-1);
    }
    private boolean dfs(int[] matchsticks, boolean[] used, int edge, int remain, int curr, int start){
        if(remain==0) return true;
        if(curr>edge) return false;
        if(curr==edge) return dfs(matchsticks, used, edge, remain-1, 0, matchsticks.length-1);
        for(int i=start; i>=0; i--){
            if(used[i]) continue;
            used[i] = true;
            if(dfs(matchsticks, used, edge, remain, curr+matchsticks[i], i-1)) return true;
            used[i] = false;
        }
        return false;
    }
}