Pythonで3種類の操作を使って配列の合計をKにできるか判定する方法

問題概要

数値のリスト nums と正の整数 K が与えられます。リストの各要素に対して、次の3つの操作のうちいずれかを1回だけ実行できます。

• その数値を負の値にする(符号を反転する)
• その数値にインデックス(1から始まる)を加算する
• その数値からインデックスを減算する

すべての要素に操作を適用した後、配列の合計がちょうど k に等しくなるようにできるかどうかを判定するのが目的です。

入力例

たとえば、nums = [1,2,3,7]、k = 8 の場合を考えてみましょう。2番目の要素「2」からインデックス「2」を引き、3番目の要素「3」からインデックス「3」を引くと、配列は [1, 0, 0, 7] となり、合計は 8 になります。したがって、出力は True です。

解法のアプローチ

この問題は、メモ化再帰(動的計画法)を用いて効率的に解くことができます。各要素について「何もしない」「符号を反転する」「インデックスを足す」「インデックスを引く」という選択肢を順に試しながら、合計が k に一致する組み合わせが存在するかを再帰的に探索します。

具体的な手順は以下の通りです。

• size := 100 としてテーブルのサイズを定義する
• 関数 is_ok() を定義する。引数は i, total, k, nums, table
• n := len(nums)(配列の長さ)とする
• total <= 0 の場合は False を返す(K は正の整数のため、それ以上探索しても意味がない)
• i >= n の場合、total == k なら True、そうでなければ False を返す
• table[i][total] が -1 でなければ、計算済みなのでその値を返す(メモ化による枝刈り)
• 現在の要素 nums[i] に対して次の4通りを試す
  • 操作なし:is_ok(i+1, total, ...)
  • 符号反転:is_ok(i+1, total - 2 * nums[i], ...)(合計から2倍引くことで反転を表現)
  • インデックス減算:is_ok(i+1, total - (i+1), ...)
  • インデックス加算:is_ok(i+1, total + i + 1, ...)
• いずれかが成功すれば table[i][total] = 1、すべて失敗すれば 0 を設定する
• メイン処理では、配列全体の合計を求め、-1 で初期化した二次元テーブルを作成して is_ok(0, total, k, nums, table) を呼び出す

Python実装例

size = 100

def is_ok(i, total, k, nums, table):
    n = len(nums)
    if total <= 0:
        return False
    if i >= n:
        if total == k:
            return True
        return False
    if table[i][total] != -1:
        return table[i][total]
    table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
    table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total]
    table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
    return table[i][total]

def solve(nums, k):
    total = sum(nums)
    table = [-1]*size
    for i in range(size):
        table[i] = [-1]*size
    return is_ok(0, total, k, nums, table)

nums = [1,2,3,7]
k = 8
print(solve(nums, k))

入力

[1,2,3,7], 8

出力

True

まとめ

このように、メモ化再帰を活用することで、各要素に対する4つの選択肢(操作なし・符号反転・インデックス加算・インデックス減算)を網羅的に探索しながら、同じ状態の再計算を回避できます。その結果、全組み合わせを素朴に試す方法と比べて大幅な高速化が可能になり、配列の合計を k にできるかどうかを効率的に判定できます。