cp_library/math/subset_sum_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Verified with

• test/atcoder/abc/abc184_f_subset_sum_fn.test.py

Code

import cp_library.math.__header__

def subset_sum(A):
    dp = [0]*(1 << len(A))
    for i,a in enumerate(A):
        for m in range(b := 1<<i):
            dp[m^b] = dp[m] + a
    return dp

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def subset_sum(A):
    dp = [0]*(1 << len(A))
    for i,a in enumerate(A):
        for m in range(b := 1<<i):
            dp[m^b] = dp[m] + a
    return dp

Back to top page