部分数列の和

847 ワード
brute force baekjoon テキストリンク

質問する


N個の整数からなる数列があり、その大きさが正の整数の部分数列のすべての要素の値がSである場合、問題は個数を求めることである.
こうそくじょうけん
ローカル数列のサイズは正の値です.

に答える


すべてのサブセットを求め,それらの和がSであると判断した.球の集合を考えなければならない.

コード#コード#

'''
Created by jun on 21/05/21
'''
# idx를 뽑거나 뽑지 않는 경우의수.
# idx 현재 판단의 기준이되는 idx / 누적합 acc
def partial_sequence(idx: int, acc: int):
    if idx == len(sequence):
        return 1 if acc == S else 0
    return partial_sequence(idx + 1, acc + sequence[idx]) + partial_sequence(idx + 1, acc)


N, S = map(int, input().split())
sequence = list(map(int, input().split()))
res = partial_sequence(0, 0)
print(res - 1 if S == 0 else res)

新知の事実


球の集合を考えなければならない.球集は1つも引かない場合の数といえるが,このときの和は0である.
部分集合の大きさが正数の場合、ゼロと空の集合を区別することはできません.したがって、Sが0の場合、セット数を削除する必要があります.
Loss function_BASE
検索バーをフックとフラットリストを使用してネイティブの反応を追加