LeetCode 473. 火柴拼正方形

Categories:

题目描述
思路分析
1. 解法一：回溯 + 剪枝（推荐）
相似题目

题目描述

✅ 473. 火柴拼正方形

思路分析

解法一：回溯 + 剪枝（推荐）

核心思路：

总长度必须能被 4 整除，目标边长为 sum / 4。

将火柴按长度降序回溯分配到 4 条边。

若当前边达到目标则继续放下一根；若某条边为 0 放失败，可剪枝避免对称重复。

复杂度分析：

时间复杂度：O(4^n)，n 为火柴数量（剪枝后更小）。

空间复杂度：O(n)，递归栈。

import java.util.Arrays;

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int v : matchsticks) {
            sum += v;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int target = sum / 4;

        Arrays.sort(matchsticks);
        int[] sides = new int[4];
        return dfs(matchsticks, matchsticks.length - 1, sides, target);
    }

    private boolean dfs(int[] sticks, int idx, int[] sides, int target) {
        if (idx < 0) {
            return sides[0] == target && sides[1] == target
                    && sides[2] == target && sides[3] == target;
        }

        int val = sticks[idx];
        for (int i = 0; i < 4; i++) {
            if (sides[i] + val > target) {
                continue;
            }

            // 尝试放入第 i 条边
            sides[i] += val;
            if (dfs(sticks, idx - 1, sides, target)) {
                return true;
            }
            sides[i] -= val;

            if (sides[i] == 0) {
                break;
            }
        }
        return false;
    }
}

import "sort"

func makesquare(matchsticks []int) bool {
	sum := 0
	for _, v := range matchsticks {
		sum += v
	}
	if sum%4 != 0 {
		return false
	}
	target := sum / 4

	sort.Ints(matchsticks)
	sides := make([]int, 4)

	var dfs func(idx int) bool
	dfs = func(idx int) bool {
		if idx < 0 {
			return sides[0] == target && sides[1] == target && sides[2] == target && sides[3] == target
		}

		val := matchsticks[idx]
		for i := 0; i < 4; i++ {
			if sides[i]+val > target {
				continue
			}

			// 尝试放入第 i 条边
			sides[i] += val
			if dfs(idx - 1) {
				return true
			}
			sides[i] -= val

			if sides[i] == 0 {
				break
			}
		}
		return false
	}

	return dfs(len(matchsticks) - 1)
}

相似题目

题目	难度	考察点
473. 火柴拼正方形	中等	回溯
698. 划分为 k 个相等的子集	中等	回溯
416. 分割等和子集	中等	回溯/DP
51. N 皇后	困难	回溯
52. N 皇后 II	困难	回溯
79. 单词搜索	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/29295027