回溯 + 动态规划（掩码 · 状态压缩），2 方法求解《473. 火柴拼正方形》
例题
473. 火柴拼正方形
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例1 ：
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
答案
回溯 · 递归
var makesquare = function(matchsticks) {
const n = matchsticks.length, sum = _.sum(matchsticks)
if (sum % 4 !== 0) return false
matchsticks.sort((a, b) => b - a)
const edges = new Uint32Array(4), edge = sum / 4
const d = (i, start) => {
if (i === n) return true
for (let j = start; j < 4; j++) {
edges[j] += matchsticks[i]
if (edges[j] <= edge && d(i + 1, start + (edges[j] === edge & 1)) === true) return true
edges[j] -= matchsticks[i]
}
return false
}
return d(0, 0)
};function makesquare(matchsticks: number[]): boolean {
const sum = matchsticks.reduce((p, v) => p + v)
if (sum % 4 !== 0) return false
const edges = new Uint32Array(4), edge = sum / 4, n = matchsticks.length
matchsticks.sort((a, b) => b - a)
const d = (i, start) => {
if (i === n) return true
for (let j = start; j < 4; j++) {
edges[j] += matchsticks[i]
if (edges[j] <= edge && d(i + 1, start + +(edges[j] === edge)) === true) return true
edges[j] -= matchsticks[i]
}
return false
}
return d(0, 0)
};class Solution {
private $n = 0;
private $edge = 0;
private $edges = array();
function makesquare($matchsticks) {
$sum = array_sum($matchsticks);
if ($sum % 4 !== 0) return false;
$this->edge = $sum / 4;
$this->n = count($matchsticks);
$this->edges = array_fill(0, 4, 0);
usort($matchsticks, function ($a, $b) {
return $a < $b;
});
return $this->d(0, 0, $matchsticks);
}
function d($i, $start, &$matchsticks) {
if ($i === $this->n) return true;
for ($j = $start; $j < 4; $j++) {
$this->edges[$j] += $matchsticks[$i];
if ($this->edges[$j] <= $this->edge && $this->d($i + 1, $start + +($this->edges[$j] === $this->edge), $matchsticks) === true) return true;
$this->edges[$j] -= $matchsticks[$i];
}
return false;
}
}func makesquare(matchsticks []int) bool {
sum := 0
for _, matchstick := range matchsticks {
sum += matchstick
}
if sum % 4 != 0 {
return false
}
sort.SliceStable(matchsticks, func(i, j int) bool {
return matchsticks[i] > matchsticks[j]
})
edge, n, edges := sum / 4, len(matchsticks), [4]int{}
var d func(i, start int) bool
d = func(i, start int) bool {
if i == n {
return true
}
for j := start; j < 4; j++ {
edges[j] += matchsticks[i]
k := 0
if edges[j] == edge {
k = 1
}
if edges[j] <= edge && d(i + 1, start + k) {
return true
}
edges[j] -= matchsticks[i]
}
return false
}
return d(0, 0)
}class Solution {
private int n = 0;
private int edge = 0;
private int[] edges = new int[4];
public boolean makesquare(int[] matchsticks) {
int sum = Arrays.stream(matchsticks).sum();
if (sum % 4 != 0) return false;
edge = sum / 4;
n = matchsticks.length;
Arrays.sort(matchsticks);
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = matchsticks[i];
matchsticks[i] = matchsticks[j];
matchsticks[j] = t;
}
return d(0, 0, matchsticks);
}
public boolean d(int i, int start, int[] matchsticks) {
if (i == n) return true;
for (int j = start; j < 4; j++) {
edges[j] += matchsticks[i];
if (edges[j] <= edge && d(i + 1, start + (edges[j] == edge ? 1 : 0), matchsticks) == true) return true;
edges[j] -= matchsticks[i];
}
return false;
}
}class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
total = sum(matchsticks)
if total % 4 != 0: return False
matchsticks.sort(reverse = True)
edge, edges, n = total / 4, [0] * 4, len(matchsticks)
def d(i, start):
if i == n: return True
for j in range(start, 4):
edges[j] += matchsticks[i]
if edges[j] <= edge and d(i + 1, start + int(edges[j] == edge)): return True
edges[j] -= matchsticks[i]
return False
return d(0, 0)动态规划 · 掩码
var makesquare = function(matchsticks) {
const n = matchsticks.length, sum = _.sum(matchsticks)
if (sum % 4 !== 0) return false
const edge = sum / 4, maxMask = 1 << n, dp = new Array(maxMask).fill(-1)
dp[0] = 0
for (let mask = 1; mask < maxMask; mask++) {
for (let i = 0; i < n; i++) {
const b = 1 << i
if (b > mask) break
if (mask & b === 0) continue
const maskPrev = mask & ~b
if (dp[maskPrev] >= 0 && dp[maskPrev] + matchsticks[i] <= edge) {
dp[mask] = (dp[maskPrev] + matchsticks[i]) % edge
break
}
}
}
return dp[maxMask - 1] === 0
};function makesquare(matchsticks: number[]): boolean {
const sum = matchsticks.reduce((p, v) => p + v)
if (sum % 4 !== 0) return false
const edge = sum / 4, n = matchsticks.length, maxMask = 1 << n, dp = new Array(maxMask).fill(-1)
dp[0] = 0
for (let mask = 1; mask < maxMask; mask++) {
for (let i = 0; i < n; i++) {
const b = 1 << i
if (b > mask) break
if ((b & mask) === 0) continue
const prevMask = mask & ~b
if (dp[prevMask] >= 0 && dp[prevMask] + matchsticks[i] <= edge) {
dp[mask] = (dp[prevMask] + matchsticks[i]) % edge
break
}
}
}
return dp[maxMask - 1] === 0
};class Solution {
function makesquare($matchsticks) {
$sum = array_sum($matchsticks);
if ($sum % 4 !== 0) return false;
$edge = $sum / 4;
$n = count($matchsticks);
$maxMask = 1 << $n;
$dp = array_fill(0, $maxMask - 1, -1);
$dp[0] = 0;
for ($mask = 1; $mask < $maxMask; $mask++) {
for ($i = 0; $i < $n; $i++) {
$b = 1 << $i;
if ($b > $mask) break;
if ($b & $mask === 0) continue;
$preMask = $mask & ~$b;
if ($dp[$preMask] >= 0 && $dp[$preMask] + $matchsticks[$i] <= $edge) {
$dp[$mask] = ($dp[$preMask] + $matchsticks[$i]) % $edge;
break;
}
}
}
return $dp[$maxMask - 1] === 0;
}
}func makesquare(matchsticks []int) bool {
sum := 0
for _, matchstick := range matchsticks {
sum += matchstick
}
if sum % 4 != 0 {
return false
}
edge, n := sum / 4, len(matchsticks)
maxMask := 1 << n
dp := make([]int, maxMask)
for i := 1; i < maxMask; i++ {
dp[i] = -1
}
for mask := 0; mask < maxMask; mask++ {
for i, v := range matchsticks {
b := 1 << i
if b > mask {
break
}
if b & mask == 0 {
continue
}
prevMask := mask & ^b
if dp[prevMask] >= 0 && dp[prevMask] + v <= edge {
dp[mask] = (dp[prevMask] + v) % edge
break
}
}
}
return dp[maxMask - 1] == 0
}class Solution {
public boolean makesquare(int[] matchsticks) {
int sum = Arrays.stream(matchsticks).sum();
if (sum % 4 != 0) return false;
int edge = sum / 4;
int n = matchsticks.length;
int maxMask = 1 << n;
int[] dp = new int[maxMask];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int mask = 1; mask < maxMask; mask++) {
for (int i = 0; i < n; i++) {
int b = 1 << i;
if (b > mask) break;
if ((b & mask) == 0) continue;
int preMask = mask & ~b;
if (dp[preMask] >= 0 && dp[preMask] + matchsticks[i] <= edge) {
dp[mask] = (dp[preMask] + matchsticks[i]) % edge;
break;
}
}
}
return dp[maxMask - 1] == 0;
}
}class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
total = sum(matchsticks)
if total % 4 != 0: return False
edge, n = total / 4, len(matchsticks)
maxMask = 1 << n
dp = [-1] * maxMask
dp[0] = 0
for mask in range(1, maxMask):
for i, v in enumerate(matchsticks):
b = 1 << i
if b > mask: break
if b & mask == 0: continue
prevMask = mask & ~b
if dp[prevMask] >= 0 and dp[prevMask] + v <= edge:
dp[mask] = (dp[prevMask] + v) % edge
break
return dp[maxMask - 1] == 0