Pythonでkで割り切れる最大合計の部分列を見つけるプログラム

問題概要

負でない整数のリストと正の整数 k が与えられたとき、要素の合計が k で割り切れる 部分列の中から、合計が最大になるものを見つけることを考えます。

例えば、入力が次のような場合を考えてみましょう。

nums = [4, 6, 8, 2], k = 2

この場合の出力は 20 になります。リスト全体の合計は 20 であり、これは 2 で割り切れるためです。

解法のアプローチ

基本的な考え方はシンプルです。まず配列全体の合計を求め、それが k で割り切れない場合は、「合計を k で割った余りと同じ余りを持つ最小の部分集合」を取り除けばよい、という発想です。具体的には以下の手順で進めます。

1. 合計の計算： 入力リスト nums の全要素の合計を numsSum として求めます。
2. 余りの計算： numsSum を k で割った余りを remainder とします。
3. 早期リターン： remainder が 0 であれば、配列全体の合計がすでに条件を満たしているため、numsSum をそのまま返します。
4. ソート： リスト nums を昇順にソートします。
5. 組み合わせの探索： nums から選べるすべての組み合わせ tpl について、その合計 subSeqSum を計算します。
6. 条件判定： subSeqSum を k で割った余りが remainder と一致する場合、numsSum − subSeqSum を返します。これが答えとなります。
7. どの組み合わせでも条件を満たせない場合は 0 を返します。

リストを事前にソートしておく理由は、itertools.combinations がソート済みのリストに対して小さい要素から順に組み合わせを生成するため、最初に見つかった条件を満たす組み合わせが「取り除くべき合計の最小値」になるからです。取り除く合計が最小であれば、残りの部分列の合計は自動的に最大になります。

実装例

それでは、実際のPythonコードを見てみましょう。

from itertools import chain, combinations

class Solution:
    def solve(self, nums, k):
        numsSum = sum(nums)
        remainder = numsSum % k
        if remainder == 0:
            return numsSum
        nums.sort()
        for tpl in chain.from_iterable(combinations(nums, r) for r in range(1, len(nums) + 1)):
            subSeqSum = sum(tpl)
            if subSeqSum % k == remainder:
                return numsSum - subSeqSum
        return 0

ob1 = Solution()
print(ob1.solve([4, 6, 8, 2], 2))

コードのポイント

• sum(nums)： リスト全体の合計を一度だけ計算することで、無駄な再計算を避けています。
• combinations(nums, r)： リストから r 個の要素を選ぶすべての組み合わせを生成します。
• chain.from_iterable(...)： 要素数 1 個から len(nums) 個までのすべての組み合わせを一つのイテレータとして連結し、順番に処理できるようにしています。

入力と出力

入力

[4, 6, 8, 2], 2

出力

20

計算量に関する注意点

この手法はすべての組み合わせを網羅的に調べるため、時間計算量は O(2^n) となり、リストのサイズが大きくなると実行時間が急激に増加します。より大きな入力に対応するには、動的計画法（DP）を用いて「各余りの状態における到達可能性」を管理したり、各余りごとの最小除去合計を追跡したりする方法が有効です。ただし、小規模な入力やアルゴリズムの学習目的であれば、本記事のシンプルな実装でも十分に機能します。

まとめ

本記事では、合計が k で割り切れる最大合計の部分列を求めるPythonプログラムを紹介しました。「全体の合計から、k で割った余りと同じ余りを持つ最小の部分集合を差し引く」という発想がポイントです。itertools モジュールを活用すれば、組み合わせの列挙も簡潔に実現できます。