【競プロ日記/Swift】深さ優先探索(部分和問題)

部分和問題

問題

配列A[A1、A2………An]が与えられる。その配列内からいくつか選択肢、その和がkと等しいか判定せよ。
※制約
・1 <= n <= 20
・-10⁸ <= a(i乗) <= 10⁸
・-10⁸ <= k <= 10⁸

解答

//以下入力値例
let array = [2,3,8]
let sumValue = 18

func equalToSumValue(count: Int, sum: Int) -> Bool
{
    // 選択管理
    if count == array.count {
        print("count:\(count),sum:\(sum)")
        return sum == sumValue
    }

    // 値未選択時
    if equalToSumValue(count: count + 1, sum: sum) {
        return true;
    }

    // 値選択時
    if equalToSumValue(count: count + 1, sum: sum + array[count]) {
        return true;
    }
    return false
}

func solve()
{
    if equalToSumValue(count: 0, sum: 0) {
        print("correct")
    } else {
        print("incorrect")
    }
}
solve()

//出力結果
//count:3,sum:0
//count:3,sum:8
//count:3,sum:3
//count:3,sum:11
//count:3,sum:2
//count:3,sum:10
//count:3,sum:5
//count:3,sum:13
//incorrect

解説

上記はbit全検索を再帰関数を用いて行う処理になります。
図で表すと下記のような流れで、全検索していきます。処理の流れとしては配列の後ろの値から選択していくので、図の一番下から上に向かって処理が行われていきます。

参考

https://drken1215.hatenablog.com/entry/2020/01/05/185000
https://qiita.com/drken/items/e77685614f3c6bf86f44