473. 火柴拼正方形

中等回溯回溯（降序 + 剪枝）力扣原题 ↗

题目描述

输入整数数组 matchsticks，matchsticks[i] 是第 i 根火柴的长度。

要用这些火柴围出一个正方形：每根火柴都必须用上，且只能用一次；火柴不能折断，但可以首尾相接组成一条边。

能围成就返回 true，否则返回 false。

示例 1

输入：matchsticks = [1,1,2,2,2]
输出：true

解释：边长为 2：两根 1 拼一条边，三根 2 各作一条边。

示例 2

输入：matchsticks = [3,3,3,3,4]
输出：false

解释：总长 16，边长须为 4；长度为 3 的四根火柴无法与其他火柴凑成 4，做不到。

数据范围

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10^8

解题思路：回溯（降序 + 剪枝）

总长不是 4 的倍数或最长的火柴超过边长时直接返回 false。否则将火柴从长到短排序，依次尝试放入 4 条边之一：放不下就跳过；若一条边和前一条边当前长度相同，放进去的结果是对称的，也跳过。全部放完即成功。

为什么正确

每条边 edges[k] 始终 ≤ side，前 i 根火柴都已分配到某条边。因为总和是 4·side，放完全部火柴时每条边恰好等于 side。

复杂度分析

最坏 O(4^n)，排序和对称剪枝后实际远小于此；递归深度 O(n)。

易错点

不排序、不做对称剪枝会超时；对称剪枝只能比较相邻两条边的当前长度，不能只跳过空边以外的情况就乱剪。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4:
            return False
        side = total // 4
        sticks = sorted(matchsticks, reverse=True)
        if sticks[0] > side:
            return False
        edges = [0] * 4

        def dfs(i):
            if i == len(sticks):
                return True
            for k in range(4):
                if edges[k] + sticks[i] > side:
                    continue
                if k > 0 and edges[k] == edges[k - 1]:
                    continue
                edges[k] += sticks[i]
                if dfs(i + 1):
                    return True
                edges[k] -= sticks[i]
            return False

        return dfs(0)

class Solution {
    int[] sticks;
    int[] edges = new int[4];
    int side;

    public boolean makesquare(int[] matchsticks) {
        long total = 0;
        for (int x : matchsticks) total += x;
        if (total % 4 != 0) {
            return false;
        }
        side = (int) (total / 4);
        int n = matchsticks.length;
        sticks = matchsticks.clone();
        Arrays.sort(sticks);
        for (int a = 0, b = n - 1; a < b; a++, b--) {
            int t = sticks[a]; sticks[a] = sticks[b]; sticks[b] = t;
        }
        if (sticks[0] > side) {
            return false;
        }
        return dfs(0);
    }

    boolean dfs(int i) {
        if (i == sticks.length) {
            return true;
        }
        for (int k = 0; k < 4; k++) {
            if (edges[k] + sticks[i] > side) {
                continue;
            }
            if (k > 0 && edges[k] == edges[k - 1]) {
                continue;
            }
            edges[k] += sticks[i];
            if (dfs(i + 1)) {
                return true;
            }
            edges[k] -= sticks[i];
        }
        return false;
    }
}

class Solution {
    vector<int> sticks;
    int edges[4] = {0, 0, 0, 0};
    int side;

    bool dfs(int i) {
        if (i == (int)sticks.size()) {
            return true;
        }
        for (int k = 0; k < 4; k++) {
            if (edges[k] + sticks[i] > side) {
                continue;
            }
            if (k > 0 && edges[k] == edges[k - 1]) {
                continue;
            }
            edges[k] += sticks[i];
            if (dfs(i + 1)) {
                return true;
            }
            edges[k] -= sticks[i];
        }
        return false;
    }

public:
    bool makesquare(vector<int>& matchsticks) {
        long long total = 0;
        for (int x : matchsticks) total += x;
        if (total % 4) {
            return false;
        }
        side = total / 4;
        sticks = matchsticks;
        sort(sticks.rbegin(), sticks.rend());
        if (sticks[0] > side) {
            return false;
        }
        return dfs(0);
    }
};

func makesquare(matchsticks []int) bool {
	total := 0
	for _, x := range matchsticks {
		total += x
	}
	if total%4 != 0 {
		return false
	}
	side := total / 4
	sticks := append([]int{}, matchsticks...)
	sort.Sort(sort.Reverse(sort.IntSlice(sticks)))
	if sticks[0] > side {
		return false
	}
	edges := [4]int{}
	var dfs func(i int) bool
	dfs = func(i int) bool {
		if i == len(sticks) {
			return true
		}
		for k := 0; k < 4; k++ {
			if edges[k]+sticks[i] > side {
				continue
			}
			if k > 0 && edges[k] == edges[k-1] {
				continue
			}
			edges[k] += sticks[i]
			if dfs(i + 1) {
				return true
			}
			edges[k] -= sticks[i]
		}
		return false
	}
	return dfs(0)
}

var makesquare = function(matchsticks) {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4 !== 0) {
        return false;
    }
    const side = total / 4;
    const sticks = [...matchsticks].sort((a, b) => b - a);
    if (sticks[0] > side) {
        return false;
    }
    const edges = [0, 0, 0, 0];
    const dfs = (i) => {
        if (i === sticks.length) {
            return true;
        }
        for (let k = 0; k < 4; k++) {
            if (edges[k] + sticks[i] > side) {
                continue;
            }
            if (k > 0 && edges[k] === edges[k - 1]) {
                continue;
            }
            edges[k] += sticks[i];
            if (dfs(i + 1)) {
                return true;
            }
            edges[k] -= sticks[i];
        }
        return false;
    };
    return dfs(0);
};

function makesquare(matchsticks: number[]): boolean {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4 !== 0) {
        return false;
    }
    const side = total / 4;
    const sticks = [...matchsticks].sort((a, b) => b - a);
    if (sticks[0] > side) {
        return false;
    }
    const edges = [0, 0, 0, 0];
    const dfs = (i: number): boolean => {
        if (i === sticks.length) {
            return true;
        }
        for (let k = 0; k < 4; k++) {
            if (edges[k] + sticks[i] > side) {
                continue;
            }
            if (k > 0 && edges[k] === edges[k - 1]) {
                continue;
            }
            edges[k] += sticks[i];
            if (dfs(i + 1)) {
                return true;
            }
            edges[k] -= sticks[i];
        }
        return false;
    };
    return dfs(0);
}

载入编辑器，自己跑一遍 →

其他解法

回溯依靠排序和剪枝在实际数据上很快，但最坏是指数级 4ⁿ；状态压缩 DP 把“哪些火柴已用”作为状态，复杂度稳定在 n·2ⁿ。

解法 2：状态压缩动态规划时间 O(n·2ⁿ)，空间 O(2ⁿ)

用 n 位二进制数 s 表示已经用掉的火柴集合。规定按顺序一条边一条边地拼，dp[s] 表示用完 s 中的火柴后，当前正在拼的那条边已有的长度，−1 表示不可达。转移时从 s 中去掉一根火柴 i，若 dp[s − i] 可达且加上 i 不超过边长，就得到 dp[s] = (dp[s − i] + i) mod 边长。最后看全集是否为 0。

复杂度有确定的上界，不依赖剪枝效果，是子集类问题的通用套路。需要 2ⁿ 的数组，n 稍大就无法使用；合法实例下往往不如带剪枝的回溯快。

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4:
            return False
        side = total // 4
        n = len(matchsticks)
        # dp[s]：用集合 s 中的火柴按顺序拼边时，当前未拼完那条边的长度；-1 表示不可达
        dp = [-1] * (1 << n)
        dp[0] = 0
        for s in range(1, 1 << n):
            for i in range(n):
                if not s >> i & 1:
                    continue
                prev = dp[s ^ (1 << i)]
                if prev >= 0 and prev + matchsticks[i] <= side:
                    dp[s] = (prev + matchsticks[i]) % side
                    break
        return dp[-1] == 0

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int x : matchsticks) total += x;
        if (total % 4 != 0) return false;
        int side = total / 4, n = matchsticks.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                if ((s >> i & 1) == 0) continue;
                int prev = dp[s ^ (1 << i)];
                if (prev >= 0 && prev + matchsticks[i] <= side) {
                    dp[s] = (prev + matchsticks[i]) % side;
                    break;
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (total % 4) return false;
        int side = total / 4, n = matchsticks.size();
        vector<int> dp(1 << n, -1);
        dp[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                if (!(s >> i & 1)) continue;
                int prev = dp[s ^ (1 << i)];
                if (prev >= 0 && prev + matchsticks[i] <= side) {
                    dp[s] = (prev + matchsticks[i]) % side;
                    break;
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
};

func makesquare(matchsticks []int) bool {
	total := 0
	for _, x := range matchsticks {
		total += x
	}
	if total%4 != 0 {
		return false
	}
	side, n := total/4, len(matchsticks)
	dp := make([]int, 1<<n)
	for i := range dp {
		dp[i] = -1
	}
	dp[0] = 0
	for s := 1; s < 1<<n; s++ {
		for i := 0; i < n; i++ {
			if s>>i&1 == 0 {
				continue
			}
			prev := dp[s^(1<<i)]
			if prev >= 0 && prev+matchsticks[i] <= side {
				dp[s] = (prev + matchsticks[i]) % side
				break
			}
		}
	}
	return dp[1<<n-1] == 0
}

var makesquare = function(matchsticks) {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4) return false;
    const side = total / 4, n = matchsticks.length;
    const dp = new Array(1 << n).fill(-1);
    dp[0] = 0;
    for (let s = 1; s < (1 << n); s++) {
        for (let i = 0; i < n; i++) {
            if (!(s >> i & 1)) continue;
            const prev = dp[s ^ (1 << i)];
            if (prev >= 0 && prev + matchsticks[i] <= side) {
                dp[s] = (prev + matchsticks[i]) % side;
                break;
            }
        }
    }
    return dp[(1 << n) - 1] === 0;
};

function makesquare(matchsticks: number[]): boolean {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4) return false;
    const side = total / 4, n = matchsticks.length;
    const dp: number[] = new Array(1 << n).fill(-1);
    dp[0] = 0;
    for (let s = 1; s < (1 << n); s++) {
        for (let i = 0; i < n; i++) {
            if (!(s >> i & 1)) continue;
            const prev = dp[s ^ (1 << i)];
            if (prev >= 0 && prev + matchsticks[i] <= side) {
                dp[s] = (prev + matchsticks[i]) % side;
                break;
            }
        }
    }
    return dp[(1 << n) - 1] === 0;
}

回溯专题的其他题目

查看回溯全部题目 →