火柴拼正方形（回溯算法）

将得到一个整数数组matchsticks ，其中matchsticks[i]是第 i 个火柴棒的长度。要用所有的火柴棍拼成一个正方形，并且不能折断任何一根火柴棒，但可以把它们连在一起，而且每根火柴棒必须使用一次。如果能拼成这个正方形，则返回true ，否则返回false。

示例 1:

输入: （存放火柴棒长度的列表matchsticks）
[1,1,2,2,2]
输出: 
True
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:
输入: （存放火柴棒长度的列表matchsticks）
[3,3,3,3,4]
输出: 
False
解释: 不能用所有火柴拼成一个正方形。

def makeSquare(matchsticks):
    totalLen = sum(matchsticks)
    if totalLen % 4 != 0:
        return False
    matchsticks.sort(reverse=True)

    edges = [0 for i in range(4)]
    def dfs(idx):
        if idx == len(matchsticks):
            return True
        for i in range(4):
            edges[i] += matchsticks[idx]
            if edges[i] <= totalLen // 4 and dfs(idx + 1):
                return True
            edges[i] -= matchsticks[idx]
        return False
    return dfs(0)

matchsticks = eval(input())
print(makeSquare(matchsticks))

#include <vector>  
#include <algorithm>  
  
bool makesquare(std::vector<int>& matchsticks) {  
    int sum = 0;  
    for (int stick : matchsticks) {  
        sum += stick;  
    }  
    if (sum % 4 != 0) {  
        return false; // 总长度不能被4整除，无法构成正方形  
    }  
    int targetSideLength = sum / 4;  
    std::sort(matchsticks.begin(), matchsticks.end()); // 将火柴棒按长度从小到大排序  
    return backtrack(matchsticks, targetSideLength, 0, 0, 0);  
}  
  
bool backtrack(std::vector<int>& matchsticks, int targetSideLength, int index, int currentSideLength, int currentSticksUsed) {  
    if (index == matchsticks.size()) {  
        return currentSideLength == targetSideLength; // 所有火柴棒都已使用，检查是否形成了正方形  
    }  
    for (int i = 0; i < 4; i++) {  
        if (currentSideLength + matchsticks[index] > targetSideLength) {  
            break; // 当前边长加上当前火柴棒的长度超过了目标边长，尝试下一个位置  
        }  
        if (currentSticksUsed + 1 > matchsticks.size()) {  
            return false; // 已经使用了超过所有火柴棒的次数，无法形成正方形  
        }  
        if (backtrack(matchsticks, targetSideLength, index + 1, currentSideLength + matchsticks[index], currentSticksUsed + 1)) {  
            return true; // 在当前位置成功形成了正方形，返回true  
        }  
    }  
    return false; // 在所有位置都无法形成正方形，返回false  
}

public boolean makesquare(int[] matchsticks) {  
    int n = matchsticks.length;  
    int sum = 0;  
    for (int matchstick : matchsticks) {  
        sum += matchstick;  
    }  
    int target = (int) Math.sqrt(sum);  
    if (target * target != sum) {  
        return false;  
    }  
    int[][] dp = new int[n + 1][target + 1];  
    for (int i = 0; i <= n; i++) {  
        Arrays.fill(dp[i], -1);  
    }  
    return dfs(matchsticks, 0, target, dp);  
}  
  
private boolean dfs(int[] matchsticks, int index, int target, int[][] dp) {  
    if (index == matchsticks.length) {  
        return target == 0;  
    }  
    if (dp[index][target] != -1) {  
        return dp[index][target] == 1;  
    }  
    for (int j = 1; j <= target; j++) {  
        if (matchsticks[index] <= j && dfs(matchsticks, index + 1, target - j, dp)) {  
            dp[index][target] = 1;  
            return true;  
        }  
    }  
    dp[index][target] = 0;  
    return false;  
}