number of combination of integers between 1 and 10, that sum to 15


Problem:

Write a function that takes an array of five integers, each of which is between 1 and 10,
and returns the number of combination of those integers that sum to 15....

For example, calling the function with the array [1, 2, 3, 4, 5] should return 1,
while calling it with [5, 5, 10, 2, 3] should return 4
(5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).

Solution:

#include <stdio.h>
#include <vector>

using namespace std;

typedef vector<int> Seq;
typedef vector<Seq> SeqOfSeq;

void sumcomb(int sum, SeqOfSeq &output, Seq &seq, int a[5], int i)
{
int val = a[i];

if(sum == val) /*Successful combination, push to output */
{
seq.push_back(val);
output.push_back(seq);
seq.pop_back();
}

if (( i + 1) < 5)
{
Seq newseq = seq;
if(sum > val) /* Include the current value in sequence */
{
seq.push_back(val);
sumcomb(sum - val, output, seq, a, i + 1);
}
sumcomb(sum, output, newseq, a, i + 1); /* Without including the current value in sequence */
}
}

int main()
{
SeqOfSeq output;

Seq seq;

int a[5];

int i = 0;
for( i = 0; i < 5; ++i)
scanf("%d", a + i);

sumcomb(15, output, seq, a, 0);

SeqOfSeq::const_iterator it;

for(it = output.begin(); it != output.end(); ++it)
{
printf("(");

Seq::const_iterator sit;

printf("%d", it->front());

for(sit = it->begin() + 1; sit != it->end(); ++sit)
{
printf(",%d", *sit);
}
printf(")\n");
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s