組み合わせ合計

概要

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

例えば , の場合、組み合わせ合計 は式 () のように表すことができる。

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

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]))