05.Scala で解く部分和問題　 Scala基礎コース

# 目次

* 【講義】全探索
* 【講義】部分和問題
* 【実習】再帰呼び出しを使った深さ優先探索の実装
* 【講義】ビット演算子
* 【講義】ビット列を使った全探索
* 【実習】ビット演算を用いた部分和問題の実装

# 【講義】全探索

今回は、プログラムが得意なジャンルの問題を取り扱ってみる。

それは全検索。
全検索とは、全部のパターンを試してみる、という問題の解き方。

例えば、簡単な数学の問題を考えてみよう。

```
382 - x = 144
```

以上の方程式を満たす整数 x はいくつだろうか。
ただし、 x は -1000 以上 1000 以下の整数とする。

普通に解くと、 382 ひく 144 で 238 が答えだが、全検索では解き方の発想が異なる。

以下のように x に代入可能なすべての整数をしらみ潰しに調べていく。

```
382 - (-1000) = 1382
382 - (-999) = 1381
382 - (-998) = 1380
...
382 - (0) = 382
...
382 - (998) = -616
382 - (999) = -617
382 - (1000) = -618
```

これらをすべて計算して、答えが 144 になるものを探し出す。
しらみ潰しに調べれば、いずれ答えは 238 というのも見つかるだろう。

このようにコンピューターは繰り返し処理や単純な判定は非常に得意。
そのため、すべてのパターンを全部合っているか確認するというのは、コンピューターが最も得意としている解き方。

このように、コンピューターで全検索を使って解くととても速く解ける問題の1つに、部分和問題という問題がある。

# 【講義】部分和問題

部分和問題とは以下のような問題。

-10億から10億までの整数 n 個で作られる数列 a が与えられる。
その中からいくつかを選び、その和が整数 k となる組み合わせが存在するかどうか、示せ。
また存在する場合には、その組み合わせも表示せよ。
なお、数列 a は最大で 20 個の整数を持ち、和の答えとなる整数 k も-10億から10億までの整数とする。

このような問題。
なお数列とは、いくつかの数を並べたもののことをいう。

問題の例としては、

```
a = (3,6,-5,7)
n = 4
k = 8
```

以上となる。
答えとしては、 `(6,-5,7)` という組み合わせで、和が 8 となるため、組み合わせは存在する、ということになる。

# 【実習】再帰呼び出しを使った深さ優先探索の実装

この部分和問題を解く時によく使われる手法が、再帰関数を使った **深さ優先探索** 。

これは、1 回の呼び出しの中で、数列の 1 番目の要素を「足す場合」と「足さない場合」の2つの再帰呼び出しをすることで、最終的にすべてのパターンを網羅する実装方法。

この再帰呼び出しの手続きを確認すると、最初に n 回再帰呼び出しをしている。
このようにパターンを樹形図で表したときのツリーを深く掘って、最初のパターンを最初に判定するような探索のことを、深さ優先探索と呼ぶ。

では早速実装してみよう。
`scala-study` フォルダの中に `PartialSumDFS.scala` というファイルを作成する。

PartialSum は英語で部分和、 DFS は Depth First Search で、深さ優先探索という意味。
まずは以下のように実装してみよう。

```scala:PartialSumDFS.scala
object PartialSumDFS extends App {
  val a = Seq(3, 6, -5, 7)
  val n = a.length
  val k = 8

  val (isMatch, result) = (false, Seq())
  if (isMatch) println(s"Yes ${result}") else println("No")
}
```

まずは、何の計算もせず、とりあえず答えが "No" となるようにする。
無事実装できたら、 sbt を起動して、

```scala:sbt
> runMain PartialSumDFS
```

以上で実行してみよう。

```scala:sbt
sbt:scala-study> runMain PartialSumDFS
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running PartialSumDFS 
No
[success] Total time: 5 s, completed 2021/07/28 9:07:49
```

このように表示されていれば成功。
コードを解説していく。

```scala
  val a = Seq(3, 6, -5, 7)
  val n = a.length
  val k = 8
```

以上は、問題文を val で定数として宣言している。

```scala
  val (isMatch, result) = (false, Seq())
```

ここでは、仮の答えを作成して isMatch と result という定数に代入している。

以上の書き方は分割代入という Scala の機能。
`()` で囲って、 `,` で区切った値のことを「タプル」という。
タプルの中の値は、 `()` で囲って、 `,` で区切った定数に割り当てることができる。

この分割代入を REPL で試してみよう。
sbt で `console` と入力して REPL を立ち上げ、

```scala:sbt_console
scala> val (a,b) = (1,"hoge")
a: Int = 1
b: String = hoge
```

以上のように入力して動作を確認してみよう。

また、タプルだけを値として扱うことも可能。

```scala:sbt_console
scala> (2, "fuga")
res0: (Int, String) = (2,fuga)
```

ただし、存在する変数に、分割代入で再代入することはできないので注意。

```scala:sbt_console
scala> var a = 1
a: Int = 1

scala> var b = "hoge"
b: String = hoge

scala> (a, b) = (2, "fuga")
<console>:1: error: ';' expected but '=' found.
       (a, b) = (2, "fuga")
              ^
```

確認できたら、 `:quit` で REPL を終了しよう。

このように以上では、 `isMatch` には true 、 `result` は、 Seq(6, -5, 7) という値になっている。

```scala
  if (isMatch) println(s"Yes ${result}") else println("No")
```

ここの if 式では、 isMatch が true であれば、 Yes と表示しその結果を出力する。
また見つからなかった場合には No と出力する。

無事、コードの雛形ができたところで、今度は深さ優先探索をする再帰関数を実装しよう。

```scala:PartialSumDFS.scala
  val n = a.length
  val k = 8

  def isMatchAndResult(index: Int, partial: Seq[Int]): (Boolean, Seq[Int]) = {
    if (index == n) {
      return if (partial.sum == k) (true, partial) else (false, Seq())
    }
    val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
    if (isMatchNotAdd) return (isMatchNotAdd, resultNotAdd)

    isMatchAndResult(index + 1, partial :+ a(index))
  }

  val (isMatch, result) = isMatchAndResult(0, Seq())
  if (isMatch) println(s"Yes ${result}") else println("No")
}
```

無事実装ができたら解説していく。

```scala
def isMatchAndResult(index: Int, partial: Seq[Int]): (Boolean, Seq[Int]) = {
```

まず、以上の isMatchAndResult 関数の宣言。
これは再帰関数のインターフェースとなる。

index は数列を走査する際の添字となる。
最初は 0 から始まり、再帰呼び出しをする度に 1 増え、最後の n - 1 番目の要素を走査し終え、 n の時の呼び出しが最後の呼び出しとなる。

partial の型は Seq[Int] で、整数のシーケンス。
この引数にはここまで足すことが決定した整数のシーケンスが含まれている。

また戻り値は、マッチしたかどうかの真偽値と、その際の結果の整数のシーケンスがタプルで返される。
ここでいうマッチとは、選び取った整数の合計値の指定された合計値が一緒になることを表すものとする。

```scala
if (index == n) {
  return if (partial.sum == k) (true, partial) else (false, Seq())
}
```

次は再帰関数の中身の処理。
まず最初に終了条件を書いておく。
index は 0 から 1 つずつ増やしていき、 n になった時に終了する。

終了時には、 a の中から選ばれた整数の合計値が partial.sum で計算され、 k と同じ場合であった場合には成功としてここまで足し合わせたシーケンスを答えとして返す。
答えはマッチしたかどうかと結果のタプルで返され、マッチした場合は (true, partial) が、マッチしなかった場合は (false, Seq()) を返す。

```scala
val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
if (isMatchNotAdd) return (isMatchNotAdd, resultNotAdd)

isMatchAndResult(index + 1, partial :+ a(index))
```

以上は、再帰呼び出しの最後に到達していない場合のコード。
ここでは、現在の添字の数列を結果に「加えない」のか「加える」かで二度再帰呼び出しを行なっている。

```scala
val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
if (isMatchNotAdd) return (isMatchNotAdd, resultNotAdd)
```

この部分は数列の要素を結果に「加えない場合」の再帰呼び出し。
`isMatchAndResult(index + 1, partial)` のように index は 1 加えるが、 partial というシーケンスはそのままに、添字を 1 つずらした再帰呼び出しを行う。
そして実行の結果もし結果がマッチしていたら、その時の答えをそのまま return 句を使ってこの関数の処理を終了させて結果を返す。

return 句は関数の中で呼び出すと、強制的にその終了が終わった時点で関数の値を返して処理を終了させる。

```scala
isMatchAndResult(index + 1, partial :+ a(index))
```

この部分は数列の要素を結果に「加える場合」の再帰呼び出し。
`isMatchAndResult(index + 1, partial :+ a(index))` のように、 index に 1 を加え、更に partial というシーケンスに、現在の添字の整数を **追加している** 。
加えない場合については既に先に判定しているので、マッチしていてもしていなくても、ここでの答えが最終的な結果になる。

無事実装できたら、 sbt を起動して、

```scala:sbt
> runMain PartialSumDFS
```

以上で実行してみよう。

```scala:sbt
sbt:scala-study> runMain PartialSumDFS
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running PartialSumDFS 
Yes List(6, -5, 7)
[success] Total time: 3 s, completed 2021/07/28 11:20:03
```

このように表示されていれば成功。
これが再帰呼び出しによる深さ優先探索を使った全探索の実装の仕方となる。

では問題が簡単なので、少し難し目の問題もやらせてみよう。

```
a = (1, 10, 49, 3, 8, 13, 7, 23, 60, -500, 42, 599, 45, -23, 1, 10, 49, 3 , 8, 13)
n = 20
k = 444
```

こうなる。
これに合わせてコードを変更してみよう。

```scala:PartialSumDFS.scala
  val a = Seq(1, 10, 49, 3, 8, 13, 7, 23, 60, -500, 42, 599, 45, -23, 1, 10, 49, 3 , 8, 13)
  val n = a.length
  val k = 444
```

無事実装できたら、 sbt を起動して、

```scala:sbt
> runMain PartialSumDFS
```

以上で実行してみよう。

```scala:sbt
sbt:scala-study> runMain PartialSumDFS
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running PartialSumDFS 
Yes List(1, 10, 49, 3, 8, 13, 7, 23, 60, -500, 42, 599, 45, 1, 10, 49, 3, 8, 13)
[success] Total time: 2 s, completed 2021/07/28 11:29:43
```

以上のように、手で計算したのではなかなか求められないような組み合わせを簡単に計算できる。

# 【講義】ビット演算子

先ほどは、再帰呼び出しによる深さ優先探索を行なったが、実はこの問題をビット列のパターンを利用して解くこともできる。

この問題で調べなくてはいけない対象は、「加える場合」と「加えない場合」の2パターンの繰り返しで表現できる。
先ほどの問題では、 2 の 20 乗のパターンがあることがわかる。
そしてこれは、コンピューターが内部的に扱っているビット列と非常に相性が良い。

前にも少し説明したが、 Scala の Int 型は、 32 ビットの符号付きの2進数で表現されている。

* 0 は 00000000 00000000 00000000 00000000
* 1 は 00000000 00000000 00000000 00000001
* 2 は 00000000 00000000 00000000 00000010
* 3 は 00000000 00000000 00000000 00000011
* 4 は 00000000 00000000 00000000 00000100
* -1 は 11111111 11111111 11111111 11111111
* -2 は 11111111 11111111 11111111 11111110

例を挙げると、このような表現がされている。
ただし、一番左端の 1 ビットだけが正負の符号を表すのに使われていることには注意が必要。

これを理解するため、一度ここで Scala でビット列を扱うためのビット演算子の紹介を行う。

Scala では、ビットの演算子は以下のようになる。

| 計算 | 演算子 | 記述例 | 結果 |
|:-:|:-:|:-:|:-:|
| ビット単位AND | & | 1 & 1 | 1 |
| ビット単位OR | ｜ | 1 ｜ 0 | 1 |
| ビット単位XOR | ^ | | 1 ^ 0 | 1 |
| ビット単位補数 | ~ | ~0 | -1 |
| 右ビットシフト (最上位ビットで埋める) | >> | -1 >> 31 | -1 |
| 右ビットシフト (0で埋める) | >>> | -1 >>> 31 | 1 |
| 左ビットシフト (0で埋める) | << | 1 << 1 | 2 |

このようになる。
たくさんあるが、1つ1つ説明していく。

## & ビット単位 AND

`&` はビット単位の AND 。
条件付き論理積である && と同様の動きをする。
REPL で確かめてみよう。

```scala:sbt_console
scala> 1 & 1
res0: Int = 1
```

1 は true と同じような扱いとなるため、 1 & 1 は 1  となったと言える。

しかし、実際に内部で行なっている計算は、以下各ビットの論理積。

```
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000001
```

両方とも 1 であるビットは一番右のビットのみなので、

```
00000000 00000000 00000000 00000001
```

となる。

別の例を見てみよう。

```scala:sbt_console
scala> -1 & 2
res2: Int = 2
```

これはビット列で見ると、以下各ビットの論理積。

```
11111111 11111111 11111111 11111111
00000000 00000000 00000000 00000010
```

両方とも 1 であるビットは一番右から2つめのビットのみ。
よって

```
00000000 00000000 00000000 00000010
```

となり、 `2` が出力される。

## ビット単位 OR (|)

`|` はビット単位の OR で、論理和を表す。
これも論理演算子の `||` と似た動きをする。

```scala:sbt_console
scala> 1 | 0
res3: Int = 1
```

は、 true || false のように 1 | 0 で 1 だが、ビット列で表すと内部的には

```
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000000
```

の各ビットの論理和になる。
結果、

```
00000000 00000000 00000000 00000001
```

以上のように 1 となる。

なお、

```scala:sbt_console
scala> -1 | 2
res4: Int = -1
```

以上の計算においては、ビット列に直すと

```
11111111 11111111 11111111 11111111
00000000 00000000 00000000 00000010
```

となるため、内部的な計算では

```
11111111 11111111 11111111 11111111
```

となり、すべてのビットが 1 である `-1` が出力される。

## ビット単位 XOR (^)

`^` は、ビット単位の XOR で排他的論理和。
A XOR B は、 A または B (ただし A かつ B ではない) というパターンのもの。

```scala:sbt_console
scala> 1 ^ 0
res5: Int = 1
```

は、 1 となる。
ビット列で表すと内部的には

```
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000000
```

の各ビットの排他的論理和になるため、結果は、

```
00000000 00000000 00000000 00000001
```

以上のように 1 となる。

なお、

```scala:sbt_console
scala> -1 ^ 2
res6: Int = -3
```

では、ビット列で表すと

```
11111111 11111111 11111111 11111111
00000000 00000000 00000000 00000010
```

となるため、内部的な計算では

```
11111111 11111111 11111111 11111101
```

となり、 `-3` が出力される。

## ビット単位補数 (~)

`~` のビット単位補数は、全ビットを反転させる演算子。

```scala:sbt_console
scala> ~0
res7: Int = -1
```

となり、ビット列で表すと内部的には、

```
00000000 00000000 00000000 00000000
```

以上のすべてのビットが反転して、

```
11111111 11111111 11111111 11111111
```

となる。
これで `-1` となる。

## ビットシフト (>>, >>>, <<)

`>>` と `>>>` と `<<` はビットをそれぞれ移動する。

```scala:sbt_console
scala> -1 >> 31
res8: Int = -1
```

これは、 -1 を右側に 31 ビットずらすというもの。

```
11111111 11111111 11111111 11111111
```

が最上位ビットで埋めながら右に 31 ビットずれて

```
11111111 11111111 11111111 11111111
```

となり、何も変わらない。
この `>>` は最上位のビットを埋めるというお約束があるので注意。

次に、 `>>>` 。

```scala:sbt_console
scala> -1 >>> 31
res11: Int = 1
```

`>>>` では、最上位ビットを 0 で埋めながら右に 31 ビットずれる。

```
11111111 11111111 11111111 11111111
```

が

```
00000000 00000000 00000000 00000001
```

となり 1 となる。

最後に、左シフトの `<<` 。

```scala:sbt_console
scala> 1 << 1
res14: Int = 2
```

以上では、左に 1 ビット 0 を埋めながらずれる。

```
00000000 00000000 00000000 00000001
```

が

```
00000000 00000000 00000000 00000010
```

となり、2 となる。
左ビットシフトは 1 ずらすと値が 2 倍になるという性質を持っている。

以上でこれでビット演算の性質が分かったのではないだろうか。
ここで習ったことを使って、 REPL でビットの中身を出力する関数を書いて、どのように表示されるかを見てみよう。

```scala
def printBits(num: Int) = {
  for (i <- 31 to 0 by -1) { if ((num & (1 << i)) != 0) print("1") else print("0") }
  println
}
```

以上を実装してみよう。
これは、 printBits という関数。
戻り値はなく、 Int のビット列をコンソールに出力する。
実装の説明をする。

```scala
for (i <- 31 to 0 by -1) { if ((num & (1 << i)) != 0) print("1") else print("0") }
```

for 式では、この `31 to 0 by -1` という記述で 1 ずつ増やすのではなく 1 ずつ減らすループも記述できる。
ここでは 31 から 0 まで i をループさせながら、与えられた整数を 1 を i だけ左シフトさせた数字の論理積を `(num & (1 << i))` で取得し、それが 0 ではない、つまり何かしらのビットが 1 であれば、 "1" を出力、なんのビットもなければ "0" を出力する。

num が 3 、 i が 1 ならば

```
00000000 00000000 00000000 00000011
00000000 00000000 00000000 00000010
```

上のような 2 つのビット列の論理積となり、

```
00000000 00000000 00000000 00000010
```

となる。
これは 0 ではないので、 1 がコンソール出力される事になる。

以下のように REPL で入力してみよう。

```scala:sbt_console
scala> def printBits(num: Int) = {
     |   for (i <- 31 to 0 by -1) { if ((num & (1 << i)) != 0) print("1") else print("0") }
     |   println
     | }
printBits: (num: Int)Unit
```

その後、実際に動きを確かめてみよう。

```scala:sbt_console
scala> printBits(1)
00000000000000000000000000000001

scala> printBits(-1)
11111111111111111111111111111111

scala> printBits(256)
00000000000000000000000100000000
```

Int の整数がどのようなビットで表現されるのか確認して、 Int がビット列で表現されていることを確かめてみよう。

# 【講義】ビット列を使った全探索

Scala で扱うデータがビット列で表現され、ビット演算子で利用できるということがわかったと思う。

では、これを使って先ほどの部分和の問題を解こうとすると、どのように表現できるだろうか。

この部分和の問題では、数列 a の最大の長さは 20 。
このビット列の右から 20 ビット分を使うとパターンが表現できそう。

数列の長さが 20 の場合には、 0 から 2 の 20 乗から 1 を引いた、 1048575 までをビットのパターンとして認識して、数列の和を確かめていけば問題が解けそう。

* 1048575 は 00000000 00001111 11111111 11111111

つまり 0 から 1048575 までカウンターを上げながら、カウンターの Int 値の下位 20 ビットを読み取っていく。
そして整数のシーケンスの添字に対して、もしビットが 1 であるならば与えられた数列の対応する添字の整数を足す、 0 であれば足さないとして、最後に目的の合計値とマッチするかを確認する。

マッチしていれば正解として終了し、もしマッチしていなければ不正解としてカウンターの数値を 1 上げてまた確認を行なっていく。
これを繰り返していく。

このようにして、ビット演算を利用してこの部分和問題を解いていこう。

# 【実習】ビット演算を用いた部分和問題の実装

では実際に実装していく。
`scala-study` フォルダに、 `PartialSumBitOp.scala` というファイルを作成して、部分和問題を解くプログラムを実装してみる。

```scala:PartialSumBitOp.scala
object PartialSumBitOp extends App {
  val a = Seq(1, 10, 49, 3, 8, 13, 7, 23, 60, -500, 42, 599, 45, -23, 1, 10, 49, 3, 8, 13)
  val n = a.length
  val k = 444

  var isMatch = false
  var bitsCounter = 0
  val max = ~(-1 << n)
  while (!isMatch && bitsCounter <= max) {
    var sum = 0
    for (i <- 0 to (n - 1)) {
      val mask = 1 << i
      val masked = bitsCounter & mask
      if (masked != 0) sum = sum + a(i)
    }
    if (sum == k) {
      isMatch = true
    } else {
      bitsCounter = bitsCounter + 1
    }
  }

  if (isMatch) {
    var result: Seq[Int] = Seq()
    for (i <- 0 to (n - 1)) {
      val mask = 1 << i
      val masked = bitsCounter & mask
      if (masked != 0) result = result :+ a(i)
    }
    println(s"Yes ${result}")
  } else {
    println("No")
  }
}
```

無事実装ができたら解説をする。

前の `PartialSumDFS` と同じ部分は解説を省く。

```scala
var isMatch = false
var bitsCounter = 0
```

これは、マッチしたかどうかのフラグを isMatch で、カウンターとなるビット列を表す Int の変数を bitsCounter で用意する。

次に、

```scala
val max = ~(-1 << n)
```

この部分は、

```
11111111 11111111 11111111 11111111
```

をまず数列の大きさ n ビット分シフトする。
仮に 20 の場合は、

```
11111111 11110000 00000000 00000000
```

となる。
さらにこれで、補数演算子を使って反転する。

```
00000000 00001111 11111111 11111111
```

これがビット列のカウンターの最大値として機能することになる。

```scala
while (!isMatch && bitsCounter <= max) {
  var sum = 0
  for (i <- 0 to (n - 1)) {
    val mask = 1 << i
    val masked = bitsCounter & mask
    if (masked != 0) sum = sum + a(i)
  }
  if (sum == k) {
    isMatch = true
  } else {
    bitsCounter = bitsCounter + 1
  }
}
```

この while 文は、和が k にマッチするのが見つかるまで、ビットカウンターを 1 ずつ進めながらループする。
最大値には先ほど作成した max を利用する。

```scala
var sum = 0
for (i <- 0 to (n - 1)) {
  val mask = 1 << i
  val masked = bitsCounter & mask
  if (masked != 0) sum = sum + a(i)
}
```

ここでは、合計値である sum を宣言した後に、 i を 0 から n - 1 までループしている。
仮に n が 1 のときには、左ビットシフトにより

```
00000000 00000000 00000000 00000010
```

1つだけビットシフトして以上のようになる。
これが定数 mask の値となる。

次に bitsCounter が、

```
00000000 00001111 11111111 11111111
```

である場合には、これと `&` で論理積が作成され、

```
00000000 00000000 00000000 00000010
```

が取得される。

このように論理積を使って特定のビット領域の値を取得することを、「マスクする」という。
またマスクに使うビット列のことをビットマスクという。

そしてこのマスクされた値が 0 ではないかを確認することによって、対象の添字のビットが 1 であることがわかる。
もし対象のビットが 1 である場合には、数列 a の添字 i の値を変数 sum に追加する。

```scala
if (sum == k) {
  isMatch = true
} else {
  bitsCounter = bitsCounter + 1
}
```

以上の実装は、もし sum が k に合致していた場合には変数 isMatch を true にして、そうでない場合には、bitsCounter を 1 加算するという実装。

以上で while 文のループの中身の解説は終了。
そして最後に、

```scala
if (isMatch) {
  var result: Seq[Int] = Seq()
  for (i <- 0 to (n - 1)) {
    val mask = 1 << i
    val masked = bitsCounter & mask
    if (masked != 0) result = result :+ a(i)
  }
  println(s"Yes ${result}")
} else {
  println("No")
}
```

以上のコードは無事「マッチした場合」には、先ほどと同じビットマスクを使って、マッチした組み合わせを result として作成し、コンソールに出力している。

「マッチしない場合」には、 No とコンソールに出力する。

では、 sbt で以下を実行してみよう。

```scala:sbt
> runMain PartialSumBitOp
```

を実行して、

```scala:sbt
sbt:scala-study> runMain PartialSumBitOp
[info] compiling 1 Scala source to /Users/glaciermelt/workspace/scala-study/target/scala-2.12/classes ...
[info] running PartialSumBitOp 
Yes List(1, 10, 49, 3, 8, 13, 7, 23, 60, -500, 42, 599, 45, 1, 10, 49, 3, 8, 13)
[success] Total time: 6 s, completed 2021/07/28 17:26:42
```

このように正解が見つかればこの実装は成功となる。

以上がビット演算を用いた部分和問題の解き方。

この実装方法では関数の呼び出し回数が減るため、再帰関数を使った方法よりもパフォーマンスは優れた実装となる。
反面、ビット演算が多く何をしているのかが読み取りにくいコードとなってしまう。

このようにビット演算を使った実装は髙いパフォーマンスが求められるライブラリの実装ではよく使われるが、チームで開発するアプリケーションなどを実装する際には、どちらの方がいいか一度考えてみる必要がある。

# まとめ

* val や var では、タプルを使った分割代入ができる
* コンピューターは全探索が得意
* 樹形図のパターンを一番深くまで行って、パターンを探索する方法を深さ優先探索という
* Scala ではビット演算を行うことができるが、可読性が落ちるため利用は気をつける必要がある

# 挑戦

## 初級

```scala:sbt_console
scala> val (a,b,c,d) = (1,"hoge",'x',0.1)
a: Int = 1
b: String = hoge
c: Char = x
d: Double = 0.1
```

## 中級

```scala:sbt_console
scala> val num = 7
num: Int = 7

scala> num << 2
res0: Int = 28
```

### 上級

```scala:sbt_console
scala> (~0 >>> 31) << 8
res10: Int = 256
```