0

Problem Definition:

Count the longest subset pairs within a set which sums to value 10. Once you have identified a pair, those 2 numbers cannot be used for forming other pairs. Output should be a number denoting count of numbers involved in such pairs.

Input :1 {1,2,8,9,1,9,1,9} Ans : 6 (3 pairs, 6 numbers, index = {0,7},{3,6},{4,5})

Input :2 {5,5,5,5,5,5,5,5} Ans : 8 (4 pairs, 8 numbers, index = {0,7},{1,6},{2,5},{3,4})

Input :3 {2,4,3,7,3,8,6,7} Ans : 4 (2 pairs, 4 numbers, index = {0,5},{3,4} or {0,5},{2,3} or {2,7},{3,4} or {1,6},{2,3} or {1,6}, {3,4})

I have written the following code:

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE 10
#define SUM 10

int d[ARRAYSIZE][ARRAYSIZE];
int count = 0;
int final[ARRAYSIZE/2];
int reset = 0;
int subset_to_sum(int a[], int m, int n, int sum)
{
    //printf("%d %d %d \t",m,n,d[m][n]);
    if (m >= n)
        return 0;
    if (d[m][n] != -1)
        return d[m][n];

    if (a[m]+a[n] == sum)
    {
        d[m][n] = 1;
        count = count+1;
        //printf("%d\n",count);
        if (m+1>=n-1)
        {
            final[reset] = count;
            reset = reset+1;
            count = 0;
        }
        else
            final[reset] = count;
        return 1+subset_to_sum(a, m+1, n-1, sum);
    }
    else if (a[m] > sum)
        return subset_to_sum(a, m+1, n, sum);
    else if(a[n] > sum)
        return subset_to_sum(a, m, n-1, sum);
    else
        return (subset_to_sum(a, m+1, n, sum)+subset_to_sum(a, m, n-1, sum)+subset_to_sum(a, m+1, n-1, sum));       
}

int main(void)
{
    int i = 0;
    int j;
    int inc;

    //int set[] = {1,2,8,9,1,9,1,9};
    //int set[] = {1,2,8,4,5,9,1,9};
    //int set[] = {2,4,3,7,3,8,6,7};
    //int set[] = {5,5,5,5,5,5,5,5};
    //int set[] = {25,35,45,5,6,7,8,9};
    //int set[] = {1,2,3,4,5,6,7,8,9,10};

    for(i=0;i<ARRAYSIZE;i++)
    {
        for(j=0;j<ARRAYSIZE;j++)
        {
            d[i][j] = -1;
        }
    }
            printf("\n");
    //printf("Total Pairs making sum %d is : %d\n",SUM,subset_to_sum(set, 0, ARRAYSIZE-1, SUM)*2);
    subset_to_sum(set, 0, ARRAYSIZE-1, SUM);

    int max = 0;
    for(i=0;i<4;i++)
    {
        if(final[i]>max)
            max = final[i];
    }
    printf("Subset Pairs making sum %d is: %d\n",SUM,max*2);
    return 0;
}

My code fails for the input : {1,2,3,4,5,6,7,8,9,10}. Could someone point to me the flaw in my approach.

Thanks!

user2761431
  • 925
  • 2
  • 11
  • 26
  • You seem to have left out two possible answers for input 3: {(1,6),(2,3)}, and {(1,6), (3,4)}. And could you please add the incorrect output you get for {1,2,3,4,5,6,7,8,9,10}? – genisage Nov 06 '14 at 22:08
  • You are right, added now. I get the output as 6 (3 pairs, 6 numbers) for the input {1,2,3,4,5,6,7,8,9,10} while the answer should be 8 (4 pairs, 8 numbers). – user2761431 Nov 06 '14 at 22:19
  • Are you required to use dynamic programming for this problem? Couldn't you just sort the list and then work your way from the ends in looking for pairs that add up to ten? I think it would be a lot easier. See [this question](http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number). – JS1 Nov 06 '14 at 22:29
  • Here's another [similar question](http://stackoverflow.com/questions/1494130/design-an-algorithm-to-find-all-pairs-of-integers-within-an-array-which-sum-to-a). – JS1 Nov 06 '14 at 22:35
  • @JS1 How do we satisfy the subset property? – user2761431 Nov 07 '14 at 05:27

1 Answers1

0

I modified your code a little bit, can you please try below:

int subset_to_sum(int a[], int m, int n, int sum)
{

if (m >= n)
    return 0;

if (a[m]+a[n] == sum)
  return 1+subset_to_sum(a, m+1, n, sum) + subset_to_sum(a, m, n-1, sum);
else
    return subset_to_sum(a, m+1, n, sum) + subset_to_sum(a, m, n-1, sum);       
}
Kaizhe Huang
  • 990
  • 5
  • 11