- # coding:utf-8
- import itertools
- def sameSums1(int_list):
- if len(int_list) == 1:
- # 列表只有一个元素必不能等分两组
- return False
- sum_of_lsit = sum(int_list)
- halfsum = sum_of_lsit / 2
- if sum_of_lsit % 2:
- # 和为奇数不可等分
- return False
- int_list.sort(reverse=True)
- for i in xrange(1, len(int_list)/2 + 1):
- if sum(int_list[:i]) < halfsum:
- # 若最大的前N位之和不足半值就不必检测N位组合的各种方案了
- continue
- elif sum(int_list[:i]) == halfsum:
- # 若恰巧是半值就直接返回
- return tuple(int_list[:i])
- for subset in itertools.combinations(int_list, i):
- sumsub = sum(subset)
- if sumsub == halfsum:
- # 找到就结束
- return subset
- if __name__ == "__main__":
- import doctest
- doctest.testmod()
- import time
- lst1 = [3, 9, 10, 30, 8]
- lst2 = [4, 5, 6, 7, 8]
- lst3 = [2, 2, 2, 3, 3]
- lst4 = [10, 9, 8, 6, 5, 3, 2, 1]
- lst5 = [74, 80, 40, 38, 80, 68, 58, 91, 65, 10, 75, 88, 47, 84, 30]
- lst6 = [97, 2, 87, 96, 24, 12, 98, 85, 99, 67, 49, 86, 65,
- 80, 83, 28, 57, 68, 90, 2, 62, 93, 9, 23]
- lst7 = [93, 99, 86, 94, 36, 62, 4, 54, 88, 69, 64, 19, 21,
- 30, 53, 24, 10, 7, 93, 46, 82, 78, 20, 45, 27, 91,
- 72, 48, 90, 62, 57, 65, 49]
- t0 = time.time()
- print sameSums1(lst1)
- print sameSums1(lst2)
- print sameSums1(lst3)
- print sameSums1(lst4)
- print sameSums1(lst5)
- print sameSums1(lst6)
- print sameSums1(lst7)
- t1 = time.time()
- print t1 - t0
- #该片段来自于http://www.codesnippet.cn/detail/0408201513328.html
来源: http://www.codesnippet.cn/detail/0408201513328.html