Pythonで配列を2つのサブ配列に分割し、合計の差が指定した数値になるか判定する方法

整数を要素とする配列「input_list」が与えられたとしましょう。この問題では、配列を2つの部分に分割したとき、それぞれの合計値の差が、あらかじめ指定された数値 n と一致するようにできるかどうかを判定します。

たとえば、input_list = [9, 2, 5, 6]、n = 0 という入力が与えられた場合、出力は「Possible」になります。[9, 2] と [5, 6] に分割すれば、両方の合計が11となり、差がちょうど0になるためです。

解決のアプローチ

この問題は、次の手順で解くことができます。

• list_total に input_list の全要素の合計を代入する
• (list_total − n) を2で割った余りが1の場合（奇数の場合）は「Not Possible」を返す
• val に (list_total − n) / 2 を代入する
• temp_sum を0で初期化する
• i を0から input_list のサイズまでループさせる
  • temp_sum に input_list[i] を加算する
  • temp_sum が val と一致した時点で「Possible」を返す
• ループが終了しても条件を満たさなければ「Not Possible」を返す

このアルゴリズムのポイントは、先頭からの累積和（プレフィックスサム）が (全体の合計 − n) / 2 と一致する位置で配列を区切ると、前半と後半の合計の差がちょうど n になるところにあります。また、(list_total − n) が奇数の場合は、整数の合計値同士で差 n を実現することができないため、最初の段階で不可能と判断できます。

それでは、実際の実装を見て理解を深めましょう。

コード例

def solve(input_list, n):
    list_total = sum(input_list)
    if (list_total - n) % 2 == 1:
        return "Not Possible"
    val = (list_total - n) / 2
    temp_sum = 0
    for i in range(0, len(input_list)):
        temp_sum += input_list[i]
        if temp_sum == val:
            return "Possible"
    return "Not Possible"

input_list = [9, 2, 5, 6]
n = 0
print(solve(input_list, n))

入力

[9, 2, 5, 6], 0

出力

Possible