划分两个相等的子序列

问题描述

给定一个整数序列,将数组分割成两个子序列,若和相等,返回两个子序列,反之返回false

问题分析

1. 将数组从中间拆分,对比两数组的和,若相等,结束.
2. 若不相等,将较大数组中的最小值移动到较小的数组中
3. 循环比较,如果不相等,重复步骤2
4. 如果循环到等于初始结果,则跳出循环,输出false;反之则相等,输出两个数组

代码

解法一

def main(data):
    total_sum = sum(data)
    if total_sum % 2 != 0:
        print("没有结果")

    if int(total_sum / 2) in data:
        print(int(total_sum / 2))

    index = int(len(data) / 2)
    # 分成两列
    left_list = data[:index]
    right_list = data[index:]

    left_sum = sum(left_list)
    right_sum = sum(right_list)

    # 判断重复节点
    result_node = []

    # 动态调整
    while left_sum != right_sum:
        # 把最小值放到较小的那一列
        if left_sum > right_sum:
            right_list.append(left_list.pop(0))
        else:
            left_list.append(right_list.pop(0))

        # 排序
        list.sort(right_list)
        list.sort(left_list)

        # 判断重复点
        if right_list in result_node:
            print("没有结果")
            break
        else:
            print('左：' + str(left_list) + ' <===>' + '右：' + str(right_list))
            result_node.append(list(right_list))

        left_sum = sum(left_list)
        right_sum = sum(right_list)

    print('结果为：' + str(left_list) + '  ' + str(right_list))


if __name__ == '__main__':
    data = [1, 5, 5, 9, 12, 14, 16, 18, 24, 23, 2, 1]
    main(data)

解法二

import itertools
import random


def canPartition(list):
    sum = 0
    for i in range(len(list)):
        sum += list[i]
    if sum % 2 == 1:
        print("无解")
        return
    count = len(list) // 2
    for i in range(1, count + 1):
        for j in itertools.combinations(list, i):
            temp = 0
            for k in range(len(j)):
                temp += j[k]
                if temp == sum / 2:
                    print(j)
                    return
    print("无解")


if __name__ == "__main__":
    list = [1, 5, 5, 9, 12, 14, 16, 18, 24, 23, 2, 1]
    # for i in range(0, 5):
    #     list.append(random.randint(1, 10))
    print(list)
    canPartition(list)