SUM exactly using K elements solution

Question

Problem: On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.

I am looking for a Dynamic Programming(DP) solution for this problem. Basically looking to understand the matrix filled approach. I wrote below program but didn't add memoization as i am still wondering how to do that.

    #include <stdio.h>
    #define SIZE(a) sizeof(a)/sizeof(a[0])
    int binary[100];
    int a[] = {1, 2, 5, 5, 100};

    void show(int* p, int size) {
            int j;
            for (j = 0; j < size; j++)
                    if (p[j])
                            printf("%d\n", a[j]);
    }

    void subset_sum(int target, int i, int sum, int *a, int size, int K) {
            if (sum == target && !K) {
                    show(binary, size);
            } else if (sum < target && i < size) {
                    binary[i] = 1;
                    foo(target, i + 1, sum + a[i], a, size, K-1);
                    binary[i] = 0;
                    foo(target, i + 1, sum, a, size, K);
            }
    }

    int main() {
            int target = 10;
            int K = 2;
            subset_sum(target, 0, 0, a, SIZE(a), K);
    }

Is the below recurrence solution makes sense?

Let DP[SUM][j][k] sum up to SUM with exactly K elements picked from 0 to j elements.

 DP[i][j][k] = DP[i][j-1][k] || DP[i-a[j]][j-1][k-1] { input array a[0....j] }

Base cases are:

DP[0][0][0] = DP[0][j][0] = DP[0][0][k] = 1
DP[i][0][0] = DP[i][j][0] = 0

It means we can either consider this element ( DP[i-a[j]][j-1][k-1] ) or we don't consider the current element (DP[i][j-1][k]). If we consider current element, k is reduced by 1 which reduces the elements that needs to be considered and same goes when current element is not considered i.e. K is not reduced by 1.

Answer 1

Your solution looks right to me.

Right now, you're basically backtracking over all possibilities and printing each solution. If you only want one solution, you could add a flag that you set when one solution was found and check before continuing with recursive calls.

For memoization, you should first get rid of the binary array, after which you can do something like this:

int memo[NUM_ELEMENTS][MAX_SUM][MAX_K]; 
bool subset_sum(int target, int i, int sum, int *a, int size, int K) {
            if (sum == target && !K) {
                    memo[i][sum][K] = true;
                    return memo[i][sum][K];
            } else if (sum < target && i < size) {
                    if (memo[i][sum][K] != -1)
                        return memo[i][sum][K];


                    memo[i][sum][K] = foo(target, i + 1, sum + a[i], a, size, K-1) || 
                                      foo(target, i + 1, sum, a, size, K);

                    return memo[i][sum][K]
            }

            return false;
    }

Then, look at memo[_all indexes_][target][K]. If this is true, there exists at least one solution. You can store addition information to get you that next solution, or you can iterate with an i from found_index - 1 to 0 and check for which i you have memo[i][sum - a[i]][K - 1] == true. Then recurse on that, and so on. This will allow you to reconstruct the solution using just the memo array.