#!/bin/python
# coding: UTF-8
# author : wenhui, 2012-6-19 9:03:03
# dscrp :
# 若对于整数N,在集合{1,2……,N}中找出m个数,
# 使其和等于剩下的N-m个数的和。返回所有可能的组合数。
# N<10000。
def _get_half_sum(total_sum, lst, lst_sum, unused_lst, ununsed_indx) :
i = ununsed_indx
if i < len(unused_lst) :
# when contains unused_list[i]
if lst_sum + unused_lst[i] == total_sum:
lst.append(unused_lst[i])
lst.sort()
print("list:", lst, "\ttotal:", sum(lst))
lst.remove(unused_lst[i])
# break
elif lst_sum + unused_lst[i] < total_sum :
elem = unused_lst[i]
# not contains unused_lst[i]
_get_half_sum(total_sum, lst, lst_sum, unused_lst, i+1)
# contains unused_lst[i]
lst.append(elem)
lst.sort()
_get_half_sum(total_sum, lst, lst_sum + elem, unused_lst, i+1)
# recover the lst & unused_lst
lst.remove(elem)
# if i < len(unused_lst)
# _get_half_sum
def get_half_sum (N) :
unused_lst = [i for i in range(1, N + 1)]
lst = []
if N * (N + 1) % 4 == 0 and N > 2:
_get_half_sum(N * (N + 1) / 4, lst, 0, unused_lst, 0)
# get_half_sum
get_half_sum(int(input("please input N: ")))
https://blog.csdn.net/ture010love/article/details/6834199