It is the well-konw Twelvefold way:

https://en.wikipedia.org/wiki/Twelvefold_way

Where we want to find the number of solutions for following equation:

X1   X2   ...   XK = target

from the given array:

vector<int> vec(N);

We can assume vec[i] > 0. There are 3 cases, for example

vec = {1,2,3}, target = 5, K = 3.

1. Xi can be duplicate and solution can be duplicate.

   6 solutions are {1,2,2}, {2,1,2}, {2,2,1}, {1,1,3}, {1,3,1}, {3,1,1}

2. Xi can be duplicate and solution cannot be duplicate.

   2 solutions are {1,2,2}, {1,1,3}

3. Xi cannot be duplicate and solution cannot be duplicate.

   0 solution.

The ides must be using dynamic programming:

dp[i][k], the number of solution of target = i, K = k.

And the iteration relation is :

if(i > num[n-1]) dp[i][k]  = dp[i-num[n-1]][k-1];

For three cases, they depend on the runing order of i,n,k. I know the result when there is no restriction of K (sum of any number of variables):

case 1:

int KSum(vector<int>& vec, int target) {
    vector<int> dp(target   1);
    dp[0] = 1;
    for (int i = 1; i <= target;   i)
        for (int n = 0; n < vec.size(); n  )
            if (i >= vec[n]) dp[i]  = dp[i - vec[n]];

    return dp.back();
}

case 2:

for (int n = 0; n < vec.size(); n  )
    for (int i = 1; i <= target;   i)

case 3:

for (int n = 0; n < vec.size(); n  )
    for (int i = target; i >= 1; --i)

When there is additional variable k, do we just simply add the for loop

for(int k = 1; k <= K; k  )

at the outermost layer?

EDIT:

I tried case 1，just add for loop of K most inside:

int KSum(vector<int> vec, int target, int K) {
    vector<vector<int>> dp(K 1,vector<int>(target   1,0));
    dp[0][0] = 1;
    for (int n = 0; n < vec.size(); n  )
        for (int i = 1; i <= target;   i)
            for (int k = 1; k <= K; k  )
            {
                if (i >= vec[n]) dp[k][i]  = dp[k - 1][i - vec[n]];
            }

    return dp[K][target];
}

Is it true for case 2 and case 3？

CodePudding user response：

In your solution without variable K dp[i] represents how many solutions are there to achieve sum i.

Including the variable K means that we added another dimension to our subproblem. This dimension doesn't necessarily have to be on a specific axis. Your dp array could look like dp[i][k] or dp[k][i].

• dp[i][k] means how many solutions to accumulate sum i using k numbers (duplicate or unique)
• dp[k][i] means using k numbers how many solutions to accumulate sum i

Both are the same things. Meaning that you can add the loop outside or inside.