(簡単解説)bit全探索-部分和問題(Python)

#はじめに
自分が勉強してきた過程で分かりにくかった箇所を簡単に解説するために投稿しています．
bit全探索とは大体どういう感じのものなのかを簡単に解説しております．
特にプログラミングを学びたての方を対象としております．
#bit全探索とは
bit全探索とは、n個の要素からなる集合の部分集合を全て調べ上げる手法のことです．
分かりにくいですよね．．．

早速例題にいきましょう

#部分和問題
3つの数字{1,2,8}の中から何個でも良いので自由に数字を選んで10を作れるか？
と言う問題をbit全探索という手法を用いて解いていきます！
#手計算で解く方法
この問題を全て書き出して解くと，{},{1},{2},{8},{1,2}{1,8},{2,8},{1,2,8}の8通りを書き出して，各々の和が10になるかを調べれば解けます．
2と8の2個({2,8})を選ぶ時に和が10となります．
#bit全探索を用いた考え方

bit全探索では，0の場合は値を未選択，1の場合は値を選択していると考えます．
今回の問題の場合，{0,0,0}だと未選択，{0,0,1}だと8のみを選択，{0,1,0}だと2のみを選択していることになります．つまり，{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}の8通りを調べ，各々の和が10になるかを調べれば解けます．(手計算だとここまででおわりです．)
この8通りを調べたあと，どの場所に1があるのかを調べないといけません．(プログラムの場合)
そこで，扱うのが論理積(&)と呼ばれるものです．これは1と1の場合のみTrueを返すものです．
つまり，1を各々の値に照らし合わせていき，Trueとなった場合に値が選択されていることがわかります！
例えば，{0,0,1}だと1を各々の値に照らし合わせていくと，8の箇所のみTrueとなります．つまり，8が選択されていることがわかります！
以上をまとめると，
1.値の選び方を全通り列挙する
2.論理積を用いて，どの箇所に1があるかを調べる
3.調べた組み合わせの和のうち10となったものが正解となる
また，2と8の2個({0,1,1})を選ぶ時が答えとなります!

#コード
コードを載せた後に詳しく説明していきます．(分かりやすく説明する為に少し冗長に記述しております)

rensyu.py

n=3
k=10
a=[1,2,8]
for bit in range(2**n):
    sum2 = 0

    for i in range(n):
        # bitにフラグが立っているかどうかを判定
        if bit & (1 << i):
            # フラグが立っていればsumに加算
            sum2 += a[n-1-i]

    if sum2 == k:
        print("Yes")
        #プログラムを終了
        exit()
print("No")

1行目：
nは数字の個数(3つ)．
kは作りたい値，
aは3つの数字の配列(リスト)を表しています．

2行目：for bit in range(2**n):
ここの部分でなぜ2のn乗までをループの範囲としているかというと，bit全探索では0と1で値を選択しているかどうかを判断していると話しました．つまり，各々の値(3つの値)に0or1の可能性があります．ですので，222=2の3乗をループの範囲としています．
bitには，0,1,2...7まで順番に入っていきます．この順番が上の方で書いた{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}に対応しています．(000,001,010,011,100,101,110,111のように2進数と考えると対応していることがわかると思います)

3行目:sum = 0
選択した値の合計値を格納する変数を定義しています．

5行目： for i in range(n):
ここの部分は上の方でも説明したように，1を移動させて，どこに1があるか(どの値が選択されているか)を調べるために，個数(3つ)をループ範囲としています．

7,9行目： if bit & (1 << i):,sum += a[n-1-i]
<<は左シフトを表しており，1を順番に1つずつ左に動かしています．({0,0,1},{0,1,0},{1,0,0})
これがTrueとなる場合1があることがわかるので，sumに該当箇所の値を加算しています．

11行目〜：if sum2 == k:
この箇所でsum2が目的の値である１０と一致しているかを判定しています．

#おわりに
もし間違っている箇所やこうした方がもっとわかりやすくなるなどご意見がございましたらコメントしていただけると助かります！！