题解 | #数组分组#

解题思路：
1. 把3，5的倍数挑出来，分别计算和
2. 采用二进制，表示分组策略（这样可以不采用递归）

# -*- coding: utf-8 -*-
# 开发者    : QSheng
# 代码文件  : HJ93 数组分组.py
# 创建时间  : 2021/7/27 10:39

class Solution:

    def __judge(self, num_oth_list, num_list_len, bin_num, sum_1, sum_2):
        """

        :param num_oth_list:
        :param i:               二进制表示
        :param sum_1:
        :param sum_2:
        :return:
        """
        # 转换为二进制，
        bin_str = bin(bin_num)[2:].zfill(num_list_len)
        bin_list = [int(i) for i in bin_str]
        sum_1_tmp, sum_2_tmp = sum_1, sum_2
        for i in range(len(bin_list)):
            if bin_list[i] == 1:
                sum_1_tmp += num_oth_list[i]
            else:
                sum_2_tmp += num_oth_list[i]
        return sum_1_tmp == sum_2_tmp

    def _split(self, num_oth_list, sum_1, limit_1, sum_2, limit_2):
        """
        判断是否可以划分
        :param num_oth_list: 剩余的数字列表
        :param sum_1:        数组一的和
        :param limit_1:      1:表示数组1当前为空， 0：表示数组1不为空
        :param sum_2:        数组二的和
        :param limit_2:      1:表示数组2当前为空， 0：表示数组2不为空
        :return:
        """
        # 边界条件
        if len(num_oth_list) == 0:
            if sum_1 == sum_2:
                return "true"
            else:
                return "false"

        # 划分两组
        # 二进制表示，1表示选择1组， 0表示选择2组
        num_list_len = len(num_oth_list)
        # start_i, end_i = limit_1, 2**num_list_len - limit_2
        start_i, end_i = 0, 2 ** num_list_len
        for i in range(start_i, end_i):
            flag = self.__judge(num_oth_list, num_list_len, i, sum_1, sum_2)
            if flag:
                return "true"
        return "false"

        # print(bin(x)[2:].zfill(10))
        # return num_oth_list, sum_1, limit_1, sum_2, limit_2

    def solve(self, num_list):

        num_5_list = list()     # 存放5的倍数
        num_3_list = list()     # 存放3的倍数
        num_oth_list = list()   # 存放其他的数字
        for num in num_list:
            if int(num % 5) == 0:
                num_5_list.append(num)
            elif int(num % 3) == 0:
                num_3_list.append(num)
            else:
                num_oth_list.append(num)

        rnt = self._split(num_oth_list
                            , sum(num_5_list), 0 if len(num_5_list) > 0 else 1
                            , sum(num_3_list), 0 if len(num_3_list) > 0 else 1)

        return rnt

import sys

if __name__ == '__main__':
    is_IDE = False
    if is_IDE:
        fr = open("data/HJ93.txt", "r", encoding="utf-8")
    else:
        fr = sys.stdin

    while True:
        line_n = fr.readline().strip()
        if line_n == "":
            break
        line_list = fr.readline().strip().split(" ")
        print(Solution().solve([int(i) for i in line_list]))


    if is_IDE:
        fr.close()