recursive function for a partition problem

Question

The problem is to find the number of times a subset of the numbers in an array add up to a specific target number.

For example, there are two ways to partition the set {1, 3, 4, 5} so that the remaining elements add up to 5:

• Select the 1 and the 4
• Select just the 5

By contrast, there is no way to partition the set {1, 3, 4, 5} to get 11.

#include "genlib.h"
#include <iostream>

void RecursePart(int[], int, int, int&);
int Wrapper(int[], int, int);


int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    cout << Wrapper(arr, 8, 11);
}


void RecursePart(int arr[], int len, int target, int& ctr) {
    if (len == 1) {
        if (arr[0] == target) {
            ctr++;
        }
        return; 
    }

    int sum, temp;
    sum = temp = arr[0];

    for (int j = 1; j < len; j++) {
        if (sum == target) {
            ctr++;
            break;
        }

        sum = sum + arr[j];

        if (sum == target) {
            ctr++;
            sum = temp;
            continue;           
        }

        if (sum > target) {
            sum = temp;
            continue;
        }

        if (sum < target) {
            temp = sum;
            continue;
        }    
    }

    RecursePart(arr + 1, len - 1, target, ctr);
}

int Wrapper(int arr[], int len, int target) {
    int n = 0;
    RecursePart(arr, len, target, n);
    return n;
}

The problem is that the output I get is 1 but the number of times a subset of the numbers in the array that add up to 11 is greater than just 1. I have tried to trace the algorithm and I know that the problem must be in the for loop. There the algorithm skips some sums. How could I override this problem?

Answer 1

Like others stated, this is the Subset Sum problem (which is NP-complete), meaning you need an exponential time algorithm to solve it.
Just by looking at your function, You call RecursePart once, each time with len-1, and then have a for-loop of length n, which means your computation is O(n^2). This obviously won't solve an O(2^n) problem.

The following is a Recursive solution that creates the sum of subsets, and tries to see if they reached the target. If there is no option for the current subset to equal target, the "creation" of the current subset is stopped.

int RecursePart(int arr[], int len, int idx, int curr_sum, int target)     
{        
    int count = 0;

    // this subset is good
    if (curr_sum == target)
       return 1;

    // the sum of the current subset exceeds target, no point in continuing
    if (curr_sum > target || idx == len)
       return 0;

    count += RecursePart(arr, len, idx+1, curr_sum + arr[idx], target);
    count += RecursePart(arr, len, idx+1, curr_sum, target);

    return count;
}

This is my previous solution, which creates all possible subsets, and the ones that match the target are counted.

#include <iostream>

int Wrapper(int[], int, int);

int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    std::cout << Wrapper(arr, 8, 11);
}

// counts the sum of a subset
int CountSet(int* arr, int* mask, int len)
{
    int sum = 0;

    for (int i=0; i < len; ++i)
    {
        if (mask[i])
        {
            sum += arr[i];
        }
    }
    return sum;
}


int RecursePart(int arr[], int idx, int len, int* subset_mask, int target) 
{
    int count = 0;

    if (idx == len)
    {
        if (CountSet(arr, subset_mask, len) == target)
            return 1;
        else
            return 0;
    }

    // create the subset "without" me
    subset_mask[idx] = 0;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    // now create the subset "with" me
    subset_mask[idx] = 1;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    return count;
}

int Wrapper(int arr[], int len, int target) {

    int* subset_mask = (int*)malloc(len*sizeof(int));
    int res = RecursePart(arr, 0, len, subset_mask, target);
    free(subset_mask);
    return res;
}

Answer 2

Since you're using C++, you an also use a vector<int> to store are the intermediate solutions like so:

#include <iostream>
#include <vector>

using namespace std;

vector<int> RecursePart(int[], int, int, int&);
int Wrapper(int[], int, int);


int main() {
    int arr[8] = {8,2,3,4,5,6,7,1};
    cout << Wrapper(arr, 8, 11);
}


vector<int> RecursePart(int arr[], int len, int target, int& ctr) 
{
    vector<int> return_vec;

    if (len == 1)
    {
        if (arr[0] == target)
        {
            ctr++;
            return return_vec;
        }

        return_vec.push_back(arr[0]);
        return return_vec;
    }

    int current = arr[0];

    if (current == target)
        ctr++;

    if (current < target)
        return_vec.push_back(current);

    vector<int> temp;

    temp = RecursePart(arr + 1, len - 1, target, ctr);

    for (int i = 0; i < temp.size(); i ++)
    {
        if (temp[i] + current == target)
        {
            ctr++;
        }

        if (temp[i] + current < target)
            return_vec.push_back(temp[i] + current);

        if (temp[i] < target)
            return_vec.push_back(temp[i]);
    }

    /*Debug Print
    cout << "Current: " << current << endl;
    for (int i = 0 ; i < return_vec.size(); i++)
    {
        cout << return_vec[i] << ", ";
    }
    cout << endl;
    */

    return return_vec;
}

int Wrapper(int arr[], int len, int target) {
    int n = 0;
    RecursePart(arr, len, target, n);
    return n;
}

To elaborate more, what's happening is we are using recursion to decompose the list into it's simplest part, which is a single number (the last element of the list), and make our return type all the possible sums that are less than our target. In the base-case, which is basically the last element of the array, if that number is equal to the target, we increment the counter, and return an empty vector, since the return-vector, which is all the possible sums less than our target, shouldn't have an element equal to or greater than our target. In all the previous recursive steps to the base-case, we get the returned vector, and then compare the current value, to all the elements in the return vector, which again, represent all the possible sums up to that point that are less than the target. We check to see if there are any sums that match the target, and then copy over any sums to our return vector that are less than the target. We then move back to the previous recursive step.

The complexity of this algorithm is still exponential ... if you enable the debug print section, you will see how the growth of the length of the vector for each iteration will grow in an exponential manner, and therefore for a given set of size N, the number of solutions you will have to check for will be in-line with O(2^N). This version of the solution though pairs that back a bit though by making sure that we only move valid solutions onto the next iteration, avoiding the need to calculate every possible subset.

Answer 3

Your function is simply wrong. You can see the same error with Wrapper(arr,4,5). You sum up elements from the left as long as they don't exceed the target, so that you can't find a solution which involves only some of those elements. You must rethink the algorithm.