473. Matchsticks to Square
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu kiểm tra xem có thể sắp xếp các que diệm thành 4 cạnh bằng nhau của một hình vuông không?
Approach
1if(total % 4 !== 0) return false;
2if (match_sticks.some((m) => m > target)) return false;1match_sticks.sort((a,b) => b - a)1if(i > 0 && sides[i] === sides[i - 1]) continue;1sides[i] += match_sticks[index]
2if(backtrack(index + 1)) return true;
3sides[i] -= match_sticks[index]Time and space complexity
Solution
1function makesquare(match_sticks: number[]): boolean {
2 const total = match_sticks.reduce((sum, val) => sum + val, 0);
3 if (total % 4 !== 0) return false;
4
5 const target = total / 4;
6 if (match_sticks.some(m => m > target)) return false;
7
8 match_sticks.sort((a, b) => b - a);
9 const sides = new Array(4).fill(0);
10
11 function backtrack(index: number): boolean {
12 if (index === match_sticks.length) {
13 return sides.every(side => side === target);
14 }
15
16 for (let i = 0; i < 4; i++) {
17 if (sides[i] + match_sticks[index] > target) continue;
18 if (i > 0 && sides[i] === sides[i - 1]) continue;
19
20 sides[i] += match_sticks[index];
21 if (backtrack(index + 1)) return true;
22 sides[i] -= match_sticks[index];
23 }
24 return false;
25 }
26
27 return backtrack(0);
28}