LeetCode 473. Matchsticks to Square

题目描述

还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。

输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

tag

回溯 DFS DP

样例

1
2
3
4
输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形,每边两根火柴。

算法1

(DFS) O()
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class :
def makesquare(self, nums: List[int]) -> bool:
def _dfs(index):
if index == len(nums):
return target[0] == target[1] == target[2] == possible_side

for i in range(4):
if target[i] + nums[index] <= possible_side:
target[i] += nums[index]
if _dfs(index + 1):
return True
target[i] -= nums[index]

return False

if len(nums) < 4 :
return False

sum_nums = sum(nums)
possible_side = sum_nums // 4
if sum_nums % 4 != 0:
return False

nums.sort(reverse = True)

target = [0] * 4;
return _dfs(0)

算法2

(DP) O()
思路

https://leetcode.com/problems/matchsticks-to-square/solution/

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution:
def makesquare(self, nums: List[int]) -> bool:

if not nums:
return False


L = len(nums)

# Possible perimeter of our square
perimeter = sum(nums)

# Possible side of our square from the given matchsticks
possible_side = perimeter // 4

# If the perimeter isn't equally divisible among 4 sides, return False.
if possible_side * 4 != perimeter:
return False

# Memoization cache for the dynamic programming solution.
memo = {}

# mask and the sides_done define the state of our recursion.
def recurse(mask, sides_done):

# This will calculate the total sum of matchsticks used till now using the bits of the mask.
total = 0
for i in range(L - 1, -1, -1):
if not (mask & (1 << i)):
total += nums[L - 1 - i]

# If some of the matchsticks have been used and the sum is divisible by our square's side, then we increment the number of sides completed.
if total > 0 and total % possible_side == 0:
sides_done += 1

# If we were successfully able to form 3 sides, return True
if sides_done == 3:
return True

# If this recursion state has already been calculated, just return the stored value.
if (mask, sides_done) in memo:
return memo[(mask, sides_done)]

# Common variable to store answer from all possible further recursions from this step.
ans = False

# rem stores available space in the current side (incomplete).
c = int(total / possible_side)
rem = possible_side * (c + 1) - total

# Iterate over all the matchsticks
for i in range(L - 1, -1, -1):

# If the current one can fit in the remaining space of the side and it hasn't already been taken, then try it out
if nums[L - 1 - i] <= rem and mask&(1 << i):

# If the recursion after considering this matchstick gives a True result, just break. No need to look any further.
# mask ^ (1 << i) makes the i^th from the right, 0 making it unavailable in future recursions.
if recurse(mask ^ (1 << i), sides_done):
ans = True
break
# cache the result for the current recursion state.
memo[(mask, sides_done)] = ans
return ans

# recurse with the initial mask with all matchsticks available.
return recurse((1 << L) - 1, 0)