Using one-dimesional array in recursion

Question

Recently I've been working on partition problem. I've done a research and I found that it can be solved using an algorithm on wiki page. Here's the pseudo algorithm:

   INPUT:  A list of integers S
   OUTPUT: True if S can be partitioned into two subsets that have equal sum
1 function find_partition( S ):
2     N ← sum(S)
3     P ← empty boolean table of size (\lfloor N/2 \rfloor  +  1) by (n + 1)
4     initialize top row (P(0,x)) of P to True
5     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
6     for i from 1 to \lfloor N/2 \rfloor 
7          for j from 1 to n
8          P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1)
9     return P(\lfloor N/2 \rfloor , n)

Using recursion you can calculate if certain sum from integers in array can be reached, if it can be reached it returns true. I start with sumOfTheIntegers/2 and I go back to 0, until I find a solution. When I found the biggest possible sum of the integers that is lower or equal to the average I calculate the difference between the the 2 groups of integers with (average-lowestSumLowerorEqualtoAverage)*2.

But then I confront with problem how can I include one dimensional array in the recursion?

Here's the code, it should probably work, but I haven't tested it yet, because of the problem. So maybe the code contains small errors. But that's not the problem, I'll fix it later.

#include <iostream>
#include <cmath>
using namespace std;
bool matrix (int a, int b)
{
    if(b == -1)  return true;
    else if (a == -1) return false;
    else if(matrix(a-1, b) == true) return true;
    else if(matrix(a-1,b-numbers[a-1]) == true) return true;
    else return false;
}
int main()
{
    int number, sum = 0;
    cin >> number;
    int numbers[number];
    for(int i = 0; i<number; i++)
    {
        cin >> numbers[i];
        sum += numbers[i];
    }
    double average = sum/2.0;
    for(int i = floor(sum/2); i!= 0; i--)
    {
        if(matrix(number+1, i) == true)
        {
            cout << abs(average-i)*2;
            break;
        }
    }
    return 0;
}

That seems way over complicated for this. Couldn't you solve this with an O(2N) solution by summing all the numbers, dividing by 2 to see if it's even (if not, there's no way to divide equally with ints), then subtract one number at a time from one end of the loop to the other until the two sub-arrays are equal or you find they can't be? — Tawnos, Mar 08 '13 at 22:48

score 1 · Accepted Answer · edited May 23 '17 at 11:49

The easiest (but certainly not the best) way is to introduce a global variable:

#include <vector>
std::vector<int> numbers;

/* ... */

int main(){
    int number;
    cin >> number;
    numbers.resize(number);
    /* ... */
}

Another possibility is to use an additional parameter:

bool matrix (int a, int b, const std::vector<int>& numbers)
{
    if(b == -1)  return true;
    else if (a == -1) return false;
    else if(matrix(a-1, b,numbers) == true) return true;
    else if(matrix(a-1,b-numbers[a-1],numbers) == true) return true;
    else return false;
}

Note that int numbers[number] is actually using a compiler-specific extension (VLA) and is not part of the C++ standard (see Does C++ support Variable Length Arrays? and Why aren't variable-length arrays part of the C++ standard?).

score 0 · Answer 2 · answered Mar 08 '13 at 22:47

0

Pass it as an argument to the function

bool matrix (int a, int b, int num_arr[])
{
  ...
  matrix(a-1,b,num_arr);
  ... 
}

answered Mar 08 '13 at 22:47

AxelOmega

974
10
18

Using one-dimesional array in recursion

2 Answers2