Pythonで配列の部分集合の和として表せない最小の正整数を求めるアルゴリズム

昇順にソートされた正の数の配列が与えられたとき、その配列の任意の部分集合の要素の合計として表すことのできない、最小の正の値を見つける必要があります。この問題は O(n) の時間計算量で解くことが求められます。

例えば、入力が A = [1, 4, 8, 12, 13, 17] の場合、出力は 2 になります。これは、1 は単独の要素として表せますが、2 はどの部分集合の合計によっても作れないためです。

解法のアプローチ

この問題は、貪欲法(Greedy法)の考え方を使うことで線形時間で解けます。手順は以下の通りです。

• n := 配列 A のサイズ
• answer := 1(初期値)
• i を 0 から n-1 まで繰り返す:
  • A[i] <= answer の場合:answer := answer + A[i]
  • それ以外の場合:ループを抜ける
• answer を返す

なぜこのアルゴリズムが機能するのか

このアルゴリズムの鍵となるのは、変数 answer が「1 から answer - 1 までのすべての値は、これまで処理した要素で表現できる」という不変条件を常に満たすように更新される点です。

次の要素 A[i] が answer 以下であれば、既存の表現可能な範囲 [1, answer - 1] の各値に A[i] を加えることで、[1, answer + A[i] - 1] の範囲全体を表現できるようになります。

逆に、A[i] が answer より大きい場合、配列は昇順ソートされているため、それ以降の要素でも answer を作ることはできません。したがって、その時点の answer が求める最小の正整数となります。

実装例

def get_smallest_element(A):
    n = len(A)
    answer = 1
    for i in range(0, n):
        if A[i] <= answer:
            answer = answer + A[i]
        else:
            break
    return answer

A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))

入力

[1, 4, 8, 12, 13, 17]

出力

2

処理の流れを追ってみる

上記の例では、以下のように処理が進みます。

• 初期状態:answer = 1
• A[0] = 1 は answer(1)以下なので、answer = 1 + 1 = 2
• A[1] = 4 は answer(2)より大きいため、ループを抜ける
• 結果として 2 を返す

計算量

配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となり、非常に効率的なアルゴリズムです。