In [ ]:
#解の個数
def number_of_solution(size, target = None):
    """
    引数1:アイテムのサイズリスト,引数2:subsetsumのtarget
    返り値 :引数1つの場合はPartitionの解となる部分集合の個数
          :引数2つの場合はtargetとなる部分集合の個数
    """
    #第2引数が与えられていない場合はPartition
    if target is None:
        target = sum(size)//2
    #テーブルの作成
    table = [[0 for j in range(target+1)] for i in range(len(size))]
    for j in range(target+1):
        for i in range(len(size)):
            #1つ目の要素
            if i == 0:
                if j == 0 or j == size[i]:
                    table[i][j] = 1
            #2つ目以降の要素
            else:
                if j >= size[i]:
                    table[i][j] = table[i-1][j-size[i]] + table[i-1][j]
                else:
                    table[i][j] = table[i-1][j]
    #print(table)
    return table[i][j]


#解の種類の個数
import collections
def kind_of_solution(size ,target = None):
    """
    引数1:アイテムのサイズリスト,引数2:subsetsumのtarget
    返り値 :引数1つの場合はPartitionの解の種類の個数
          :引数2つの場合はtargetとなる種類の個数
    """
    #第2引数が与えられていない場合はPartition
    if target is None:
        target = sum(size)//2
    #アイテムのサイズごとの個数を持つ辞書
    number_of_items = collections.Counter(size)
    #アイテムのサイズを持つリスト
    number_of_types = list(number_of_items.keys())
    #テーブルの作成
    table = [[0 for j in range(target+1)] for i in range(len(number_of_types))]

    for j in range(target+1):
        for i in range(len(number_of_types)):
            #1つ目の要素
            if i==0:
                for k in range(number_of_items[number_of_types[i]]+1):
                    if k*number_of_types[i] == j:
                        table[i][j] = 1
            #2つ目以降の要素
            else:
                table[i][j] = sum(table[i-1][j-k*number_of_types[i]] for k in range(number_of_items[number_of_types[i]]+1) if j >= k*number_of_types[i])
    #print(table)
    return table[i][j]



size = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4]
print(number_of_solution(size,495))
print(number_of_solution(size))
print(kind_of_solution(size))