题目

题目1
将一个长度为n（n>0）的整型数组分割成两个数组，要求这两个数组的和之差最小
题目2
任意交换两个长度都为为n（n>0）的整型数组的元素，要求最终这两个数组的和之差最

问题分析

对于第二个问题，我们可以将两个数组合成一个长度为2n的数组，变成类似问题1的数组分隔问题。但它多了一个要求：分割后的两个数组长度都为n。
针对这种分割问题，我们可以采用二叉树的思路（TODO后续补图）

• 对于一个长度为n(n>0)的数组任意分割（题目1）可能的情况为O(pow(2, n-1))。
• 对于一个长度为2n(n>0)的数组平均分割（题目2）可能的情况为O(combinations(list_, n))。

代码实现

题目1

def depart_list(list_):
    _size = len(list_)
    _av = sum(list_)/2
    print('average:{}'.format(_av))

    _min = _av
    _min_seq = 0
    for i in range(0, pow(2, _size - 1)):
        _total = 0
        for j in range(0, _size):
            _total += list_[j]*((i>>j)&1)
    
        if abs(_total - _av) < _min:
            _min = abs(_total - _av)
            _min_seq = i
    
    print(_total)
    print(_min)
    print(_min_seq)
    _ret = []
    for k in range(0, _size):
        if _min_seq & (1<<k):
            _ret.append(list_[k])

    return _ret

depart_list([1231,35,46,6667,235,2563])
### [6667]

题目2：

def av_depart_list(list_):
    _size = len(list_)
    if _size % 2 != 0:
        return None

    _size_ret = _size/2
    _av = sum(list_)/2
    print("average:{}".format(_av))
    
    _min = _av
    _min_seq = 0
    for i in range(0, pow(2, _size - 1)):
        if bin(i)[2:].count('1') != _size_ret:
            continue
        
        _total = 0
        for j in range(0, _size):
            _total += list_[j]*((i>>j)&1)
    
        if abs(_total - _av) < _min:
            _min = abs(_total - _av)
            _min_seq = i
    
    print(_min)
    print(_min_seq)
    _ret = []
    for k in range(0, _size):
        if _min_seq & (1<<k):
            _ret.append(list_[k])

    return _ret

av_depart_list([1231,35,46,6667,235,2563])
### [35, 46, 6667]