Rで部分和問題をbit全探索で解く

• Rでは、expand.grid関数を使うと、引数のベクトルの全組み合わせを列挙できる
• 下記のように、引数を0:1にして5個繋げれば、 2⁵ =32 通りの組み合わせを表示可能

長さ5、各要素が 1 か 0 のタプルを作成

> Pattern <- expand.grid(0:1, 0:1, 0:1, 0:1, 0:1)
> Pattern
   Var1 Var2 Var3 Var4 Var5
1     0    0    0    0    0
2     1    0    0    0    0
3     0    1    0    0    0
4     1    1    0    0    0
5     0    0    1    0    0
6     1    0    1    0    0
7     0    1    1    0    0
8     1    1    1    0    0
9     0    0    0    1    0
10    1    0    0    1    0
11    0    1    0    1    0
12    1    1    0    1    0
13    0    0    1    1    0
14    1    0    1    1    0
15    0    1    1    1    0
16    1    1    1    1    0
17    0    0    0    0    1
18    1    0    0    0    1
19    0    1    0    0    1
20    1    1    0    0    1
21    0    0    1    0    1
22    1    0    1    0    1
23    0    1    1    0    1
24    1    1    1    0    1
25    0    0    0    1    1
26    1    0    0    1    1
27    0    1    0    1    1
28    1    1    0    1    1
29    0    0    1    1    1
30    1    0    1    1    1
31    0    1    1    1    1
32    1    1    1    1    1

• これを用いて、全探索を行ってみる

• 例えば、下記の部分和問題を全探索で解くことを考える

• 例題はこちらから引用：こわくないbit全探索2 基本編1
  

• N=5, A={1,2,3,6,8},W=10の場合を考えてみる

部分和問題を全探索で解く

Pattern <- expand.grid(0:1, 0:1, 0:1, 0:1, 0:1)
A <- c(1, 2, 3, 6, 8)
L <- 5
W <- 10
ans <- 0

for( j in 1:nrow(Pattern)){
    Combi <- c()
    for( i in 1:L ){
        if(Pattern[j,i]){
            Combi <- append(Combi,A[i])
        }
    }
    if( sum(Combi) == W){
        ans = ans + 1
    }
}
print(ans)

こんな感じ？