組み合わせ合計

概要

組み合わせ合計 (combination sum) 問題は、正の整数の集合 \(\vector{x} = \{x_0,x_1,\ldots\}\) の中から合計が値 \(y\) になるようなすべての一意の組み合わせを選択する問題。ナップサック問題 (Knapsack problem) の一種でしばしばプログラミング課題として用いられる。

例えば \(y=8\), \(\vector{x} = \{2,3,4,6\}\) の場合、組み合わせ合計 \(S_8\) は式 (\(\ref{cs4}\)) のように表すことができる。\[ \begin{equation} S_8 = \{ \{2,2,2,2\}, \{2,2,4\}, \{2,3,3\}, \{2,6\}, \{4,4\} \} \label{cs4} \end{equation} \]

現実の適用例としては、ストリームやパイプラインの設計においてデータの分割位置で挙動が変わらないことを確認するために、分割されるデータチャンクのそれぞれの長さを決定するようなケースで使用することができる。

def combination_sum(target, nums):

    def _cs(target, nums, curr, result):
        if target == 0:
            result.append(list(curr))
            return
        elif len(nums) == 0:
            return
        elif target - nums[0] >= 0:
            curr.append(nums[0])
            _cs(target - nums[0], nums, curr, result)
            curr.pop()
        _cs(target, nums[1:], curr, result)
        return

    result = []
    _cs(target, nums, [], result)
    return result

# [[2, 2, 2, 2], [2, 2, 4], [2, 3, 3], [2, 6], [4, 4]]
print(combination_sum(8, [2, 3, 4, 6]))