ALDS1_5_A:

この問題は、$n$ の値が小さいので、数列の要素を選ぶ組み合わせを列挙するアルゴリズムが適用できます。各要素について選択するかしないかの2択となるので、$2^n$ 通りの組み合わせがあります。これらは次の再帰によるアルゴリズムで生成することができます。

# n個の要素から0個以上を選ぶ組み合わせを列挙する
def make_combination(n):
    state = [False] * n # 各要素を False で初期化した要素数nのリストを生成する
    select(n, state, 0)

# i 番目の要素を含めるか含めないかを決める
def select(n, state, i):
    if i == n:
        print(state)
        return

    select(n, state, i + 1)
    state[i] = True  # i 番目の要素を含めるを選択する
    select(n, state, i + 1)
    state[i] = False  # i 番目の要素を含めない

$state$ を $state[i]$ が True のとき $i$ 番目の整数を選択する、False のとき選択しない、という配列とします。最初の要素から選択するかしないかを再帰関数によって分岐させ、 $i$ が $n$ に達したときの $state$ が１つの組み合わせを保持しています。0 から $2^n − 1$ までのビット列が生成されることになります。

この再帰関数により、$i$ 番目の要素を選ぶか選ばないかの全ての組み合わせを調べることができます。たとえば、$n$ が 3 のとき $select(0)$ は $state$ に記録されるビット列として、$[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]$ を順番に生成します。

ここでは、この考え方を応用し、次のような１つの関数を定義して問題を解くことにします。$solve(i, m)$ を「$i$ 番目以降の要素を使って $m$ を作れる場合 True を返す」という関数とすると、$solve(i, m)$ は以下の２つの部分問題に分割することができます。

• $solve(i + 1, m)$: $i$ 番目の要素を「使わずに」$i+1$番目、つまり次の要素に進む
• $solve(i+1, m - A[i])$: $i$ 番目の要素を「使い」$i+1$番目、つまり次の要素に進む

これらを再帰的に調べることで元の問題である $solve(0, m)$ を判定することができます。

def solve(i, m, n, A):
    if m == 0:
        return True
    if i >= n:
        return False

    return solve(i + 1, m, n, A) or solve(i + 1, m - A[i], n, A)

$solve(i, m)$ において、与えられた整数を作ることができたとき、$m$ が 0 となります。また $m$ が $0$ より大きくかつ $i$ が $n$ 以上になったときに与えられた整数は作れなかったことになります。部分問題である $solve(i+1, m)$ か $solve(i+1, m - A[i])$ のいずれかが True のとき、元の問題 $solve(i, m)$ が True になります。

たとえば、次の例は数列 $A = [1, 5, 7]$ に対して、8 が作れるかどうかを判定している様子です。

再帰による問題の分割

この例では、「1 を選ぶ」$\rightarrow$ 「5 を選ばない」$\rightarrow$「7 を選ぶ」の組み合わせで 8 を作ることができます。関数の中で i 番目の要素を選ぶか選ばないかについてさらに２つの関数を呼び出します。

再帰関数の中で２つの再帰関数を呼び出すことを繰り返せば、$O(2^n)$ のアルゴリズムとなり、全ての組み合わせを調べる方法は大きな $n$ に対しては適用することができません。

このアルゴリズムでは $(i, m)$ の組について $solve(i, m)$ が複数回計算されてしまう無駄があります。これは動的計画法と呼ばれるテクニックで改善することができます。

Reference

---