部分和問題を総当たりで解く (Python) - Qiita

N個の整数の部分和を総当たりで求める求める方法 動的計画法の練習(？)をする中で、総当たりして結果を確認したいけど総当たりのいい感じのコードがなかなか見付からなかったのでメモしておく。 大まかな手順 整数の組み合わせは配列Aで与える 2^N 個のビットマスクを行列で作成する [0,0,0,...] [0,1,0,...] 各ビットマスクの行列 * Aを計算する A = (1,2,3) N=len(A) # ビットマスク作成 bitmask = [list(map(int, list(('0'*N + (bin(i))[2:])[-N:]))) for i in range(2 ** N)] # ビットマスクごとに部分和を計算 for mask in bitmask: print(mask,sum( [a*b for a,b in zip(mask,A)] ))