473. Matchsticks to Square
Link: https://leetcode.com/problems/matchsticks-to-square/
Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be usedexactlyone time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input:
[1,1,2,2,2]
Output:
true
Explanation:
You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input:
[3,3,3,3,4]
Output:
false
Explanation:
You cannot find a way to form a square with all the matchsticks.
Note:
- The length sum of the given matchsticks is in the range of
0to10^9 - The length of the given matchstick array will not exceed
15
Solution:
Use recursion to try to put these match sticks into 4 groups. (DFS: Depth First Search)
class Solution(object):
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums or len(nums) < 4:
return False;
sum_len = sum(nums)
if sum_len % 4 != 0:
return False
# The reason we sort and reverse nums is that
# in the recursion,
# if each time we can try the longer matchstick first,
# then the bad solution will quit the pipe 'or' statement earlier.
nums.sort()
nums.reverse()
border_len = sum_len / 4
sums = [0 for _ in xrange(4)]
return self.makesquare_helper(nums, 0, sums, border_len)
def makesquare_helper(self, nums, index, sums, border_len):
# base case
if sums[0] > border_len or sums[1] > border_len or sums[2] > border_len or sums[3] > border_len:
return False
if index >= len(nums):
if sums[0] == sums[1] == sums[2] == sums[3] == border_len:
return True
return False
n = nums[index]
for i in xrange(4):
if sums[i] + n > border_len:
continue
sums[i] += n
# recursion.
if self.makesquare_helper(nums, index + 1, sums, border_len):
return True
sums[i] -= n
return False
Note:
- Do not forget to check 'if sums[i] + n > border_len' in the recursion.
- The above solution's time complexity = O(4 power of n), n is the number of match sticks.
class Solution(object):
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums or len(nums) < 4:
return False;
sum_len = sum(nums)
if sum_len % 4 != 0:
return False
# The reason we sort and reverse nums is that
# in the recursion,
# if each time we can try the longer matchstick first,
# then the bad solution will quit the pipe 'or' statement earlier.
nums.sort()
nums.reverse()
border_len = sum_len / 4
sum1, sum2, sum3, sum4 = 0, 0, 0, 0
return self.makesquare_helper(nums, 0, sum1, sum2, sum3, sum4, border_len)
def makesquare_helper(self, nums, index, sum1, sum2, sum3, sum4, border_len):
# base case
if sum1 > border_len or sum2 > border_len or sum3 > border_len or sum4 > border_len:
return False
if index >= len(nums):
if sum1 == border_len and sum2 == border_len and sum3 == border_len and sum4 == border_len:
return True
else:
return False
# check the current num belongs to which border
num = nums[index]
return self.makesquare_helper(nums, index + 1, sum1 + num, sum2, sum3, sum4, border_len) or\
self.makesquare_helper(nums, index + 1, sum1, sum2 + num, sum3, sum4, border_len) or\
self.makesquare_helper(nums, index + 1, sum1, sum2, sum3 + num, sum4, border_len) or\
self.makesquare_helper(nums, index + 1, sum1, sum2, sum3, sum4 + num, border_len)
Note:
- The above solution's time complexity = O(4 power of n), n is the number of match sticks.
- Explanation for time complexity: There are 4 branches in the recursion, and each one try to go through n match sticks.
Time Limited Exceeded
Calculate all permutations of the given nums, and try to separate 4 groups on each permutation. And try to find whether there exits permutation whose groups satisfy the conditions.
import time
class Solution(object):
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums or len(nums) < 4:
return False;
sum_len = sum(nums)
if sum_len % 4 != 0:
return False
border_len = sum_len / 4
# Calculate all unique permutations.
permutations = self.get_unique_permutations(nums)
l = len(nums)
for permutation_nums in permutations:
for i in xrange(1, l - 2):
for j in xrange(i + 1, l - 1):
for k in xrange(j + 1, l):
if sum(permutation_nums[:i]) == border_len and\
sum(permutation_nums[i:j]) == border_len and\
sum(permutation_nums[j:k]) == border_len and\
sum(permutation_nums[k:]) == border_len:
print permutation_nums
return True
return False
def get_unique_permutations(self, arr):
if not arr:
return []
index_set = set()
result_set = set()
results = []
buff = []
self.get_unique_permutations_helper(arr, index_set, result_set, results, buff)
return results
def get_unique_permutations_helper(self, arr, index_set, result_set, results, buff):
# base case
if len(buff) == len(arr):
result_str = ','.join([str(x) for x in buff])
if result_str not in result_set:
result_set.add(result_str)
results.append(list(buff))
buff = []
return
for i in xrange(len(arr)):
if i in index_set:
continue
index_set.add(i)
buff.append(arr[i])
# recursion
self.get_unique_permutations_helper(arr, index_set, result_set, results, buff)
buff.pop()
index_set.remove(i)
if __name__ == '__main__':
print 'Program is working'
start_time = time.time()
# nums = [1,1,2,2,2]
# nums = [3,3,3,3,4]
nums = [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
solution = Solution()
print solution.makesquare(nums)
print 'Program is end, time cost = {}'.format(time.time() - start_time)
Note:
- The above solution's time complexity = O(n! * (n power of 3) ).