AIM:Program to solve Subset sum problem.

Desrcription:

In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: Given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero. The problem is NP-complete. Input: The number of elements. The Weights of each element. Total Required Weight. Output:Subsets in which the sum of elements is equal to the given required weight(input).

CODE:

#include <iostream>
using namespace std;

// Constant definitions
const int MAX = 100;

// class definitions
class SubSet
{
    int stk[MAX], set[MAX];
    int size, top, count;
    public:
    SubSet()
    {
        top = -1;
        count = 0;
    }
    void getInfo(void);
    void push(int data);
    void pop(void);
    void display(void);
    int fnFindSubset(int pos, int sum);
};

/******************************************************************************
*Function   : getInfo
*Description: Function to read input
*Input parameters: no parameters
*RETURNS    : no value
******************************************************************************/

void SubSet :: getInfo(void)
{
    int i;
    cout << "Enter the maximum number of elements : ";
    cin >> size;

    cout << "Enter the weights of the elements : \n";
    for (i=1; i<=size; i++)
        cin >> set[i];

}

/******************************************************************************
*Function   : push
*Description: Function to push an element on to the stack
*Input parameters: 
*int data   - value to be pushed on to the stack
*RETURNS    : no value
******************************************************************************/
void SubSet :: push(int data)
{
    stk[++top] = data;
}

/******************************************************************************
*Function   : pop
*Description: Function to pop an element from the stack
*Input parameters: no parameters
*RETURNS    : no value
******************************************************************************/

void SubSet :: pop(void)
{
    top--;
}

/******************************************************************************
*Function   : display
*Description: Function to display solution to sub set sum problem
*Input parameters: no parameters
*RETURNS    : no value
******************************************************************************/
void SubSet :: display()
{
    int i;
    cout << "\nSOLUTION #"<< ++count <<" IS\n{ ";
    for (i=0; i<=top; i++)
        cout << stk[i] << " ";

    cout << "}" << endl;
}

/******************************************************************************
*Function   : fnFindSubset
*Description    : Function to solve Subset sum problem.
*Input parameters:
*   int pos - position
*   int sum - sum of elements
*RETURNS    : returns 1 if solution exists or zero otherwise
******************************************************************************/
int SubSet :: fnFindSubset(int pos, int sum)
{
    int i;
    static int foundSoln = 0;

    if (sum>0)
    {
        for (i=pos; i<=size; i++)
        {
            push(set[i]);
            fnFindSubset(i+1, sum - set[i]);
            pop();
        }
    }

    if (sum == 0)
    {
        display();
        foundSoln = 1;
    }

    return foundSoln;
}

/******************************************************************************
*Function   : main
*Input parameters: no parameters
*RETURNS    :   0 on success
******************************************************************************/
int main(void)
{
    int i,sum;

    SubSet set1;

    set1.getInfo();
    cout << "Enter the total required weight : ";
    cin >> sum;

    cout << endl;

    if (!set1.fnFindSubset(1, sum))
        cout << "\n\nThe given problem instance doesnt have any solution." << endl;
    else
        cout << "\n\nThe above-mentioned sets are the required solution to the given instance." << endl;

    return 0;
}

OUTPUT

SAMPLE 1

Enter the maximum number of elements : 5

Enter the weights of the elements :

1 2 3 4 5

Enter the total required weight : 5

SOLUTION #1 IS

{ 1 4 }

SOLUTION #2 IS

{ 2 3 }

SOLUTION #3 IS

{ 5 }

The above-mentioned sets are the required solution to the given instance.

SAMPLE 2

Enter the maximum number of elements : 4

Enter the weights of the elements :

1 2 3 4

Enter the total required weight : 11

The given problem instance doesnt have any solution.