C++で解く「組み合わせの総和IV」――メモ化再帰による実装方法

問題概要

すべての要素が正の整数で、かつ重複のない整数配列が与えられたとします。このとき、要素を足し合わせて正の整数 target になる組み合わせが何通りあるかを求めるのが本問題です。順序が異なる並びは、別々の組み合わせとして数える点に注意してください。

例えば、配列が [1, 2, 3]、ターゲットが 4 の場合、考えられる組み合わせは [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2,2]] の7通りとなるため、出力は 7 になります。

解法のアプローチ

この問題は、メモ化再帰（トップダウン型の動的計画法）を用いることで効率的に解けます。手順は以下の通りです。

• 再帰関数 solve() を用意します。引数として、配列・ターゲット・動的計画法（メモ化）用の配列を受け取ります。
• target が 0 の場合は 1 を返します（組み合わせが1通り完成したことを意味します）。
• dp[target] が -1 以外（計算済み）であれば、その値を返します。
• ans を 0 で初期化します。
• i を 0 から nums の要素数までループします。
  • target >= nums[i] の場合、ans := ans + solve(nums, target - nums[i], dp) を実行します。
• dp[target] に ans を格納します。
• ans を返します。

一度計算したターゲット値の結果を dp 配列にキャッシュすることで、同じ状態の再計算を避けられます。時間計算量は O(target × n)（n は配列の要素数）、空間計算量は O(target) となります。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector <int> dp(target + 1, -1);
        return helper(nums, target, dp);
    }
    int helper(vector <int>& nums, int target, vector <int>& dp){
        if(target == 0)return 1;
        if(dp[target] != -1)return dp[target];
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            if(target >= nums[i]){
                ans += helper(nums, target - nums[i], dp);
            }
        }
        return dp[target] = ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3};
    cout << ob.combinationSum4(v, 4);
}

入力

[1,2,3]
4

出力

7