forked from ngiengkianyew/daily-coding-problem
-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem_060.py
29 lines (21 loc) · 794 Bytes
/
problem_060.py
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
def partition_helper(mset, start, end, outer_sum, inner_sum):
if start >= end:
return False
if outer_sum == inner_sum:
return True
return \
partition_helper(mset, start + 1, end, outer_sum + mset[start],
inner_sum - mset[start]) or \
partition_helper(mset, start, end - 1, outer_sum + mset[end],
inner_sum - mset[end])
def can_partition(mset):
if not mset:
return True
if sum(mset) % 2 == 1:
return False
mset.sort()
return partition_helper(mset, 0, len(mset) - 1, 0, sum(mset))
assert can_partition([15, 5, 20, 10, 35, 15, 10])
assert not can_partition([15, 5, 20, 10, 35])
assert can_partition([1, 2, 3, 4, 9, 1])
assert can_partition([1, 1, 1, 1, 1, 1, 6])