Tutorial: Sum of All Possible Subsets of A Number in Java

by eturo

Before I will end my day, I would like to share a program source code to solve a problem which I think it's a little bit complicated. This was given when I once attended a seminar-workshop in our region. I made a Java applet for the said problem as shown below.

Computing All Subset Sums

Problem: Given an array containing some integers (there may be duplicates), write a" routine that returns all the possible sums that can be formed by using numbers in the array. For instance, if the array contains 4 and 6, the possible sums are n0, 4, 6, and 10." If the array contains 1, 3, 5, and 7, the possible sums are 0, 1, 3, 5, 7, 4, 6, 8, 8, 10, 12, 9, 11, 13, 15, and 16. Notice that 8 appears twice in the answer (1+7 and 3+5).". 

The Design:

 

Program Testing

 

You should specify first the size of the array by entering it into the text box (text field in Java). Then, you will enter now the elements or number to be stored in the array. As you type, it will be shown in the upper left text area. If you enter elements which beyond the size of the array, then an error message will be displayed. To display ALL THE POSSIBLE SUM OF ALL THE SUBSETS OF NUMBERS IN THE ARRAY, click the PRINT ALL POSSIBLE SUMS button below. To Reset or Clear the elements in the Array to enter new elements, click the RESET/CLEAR ARRAY button. (see the example output below)

First Test:

Second Test:

Note: The elements I entered in my Java applet were came or based from the given numbers in the given problem stated above.

The Program Source Code:

Here is the source code I want to share to you guys. The program is a little bit complicated but I guessed you can make the solution if you strive to finish it with focused and good algorithms for your program.

/**
 *
 * @author (Vilchor G. Perdido)
 * @date (April 14, 2010)
 */

import java.awt.*;
import java.applet.*;
import java.awt.event.*;

public class SumOfSubsetNumbers extends Applet implements ActionListener {

    Button bPrintSum,bReset;
    TextField txtSize,txtInput;
    List listElements = new List();
    List listSums = new List();
    Label lblElements,lblSize;
    int arraySize;
    int []arrayElements;
    int elements = 0;
    int temp = 0;
    int index = 0;
    int num, data, ctr, possibleSum, subIndex, valueOfSum;
    Font myFont,otherFont,buttonFont;

    public void init()
    {
        showStatus("Developed by: Vilchor G. Perdido");
       
        setLayout(null);
        setSize(550,660);
        myFont = new Font("Arial",Font.BOLD,14);
        otherFont = new Font("Arial",Font.BOLD,18);
        buttonFont = new Font("Arial",Font.BOLD,16);
        setBackground(Color.darkGray);

        listElements.add("===============================");
        listElements.add("SIZE AND ELEMENTS OF THE ARRAY");
        listElements.add("===============================");
        listElements.setBounds(10,30,260,200);
        listElements.setFont(myFont);
        listElements.setBackground(Color.yellow);
        add(listElements);
       
        listSums.add("===============================");
        listSums.add("  Possible SUMS of the ELEMENTS");
        listSums.add("===============================");
        listSums.setBounds(10,250,260,400);
        listSums.setFont(myFont);
        listSums.setBackground(Color.yellow);
        add(listSums);

        lblSize = new Label("WHAT IS THE SIZE OF THE ARRAY?");
        lblSize.setBounds(290,50,500,30);
        lblSize.setForeground(Color.white);
        add(lblSize);
       
        txtSize = new TextField();
        txtSize.setBounds(290,80,200,30);
        add(txtSize);
       
        lblElements = new Label("ENTER THE ELEMENTS OF THE ARRAY");
        lblElements.setBounds(290,120,500,30);
        lblElements.setForeground(Color.white);
        add(lblElements);
       
        txtInput = new TextField();
        txtInput.setBounds(290,150,200,30);
        add(txtInput);
       
        bPrintSum = new Button("PRINT all possible SUMS");
        bPrintSum.setBounds(300,500,210,30);
        bPrintSum.setEnabled(false);
        bPrintSum.setFont(buttonFont);
        add(bPrintSum);
       
        bReset = new Button("RESET / CLEAR Array");
        bReset.setBounds(300,540,210,30);
        bReset.setEnabled(false);
        bReset.setFont(buttonFont);
        add(bReset);
               
        txtSize.addActionListener(this);
        txtInput.addActionListener(this);
        bPrintSum.addActionListener(this);
        bReset.addActionListener(this);
    }
   
    public void paint(Graphics g)
    {
        showStatus("Developed by: Vilchor G. Perdido");
    }
  
    public void actionPerformed(ActionEvent evt)
    {     
       
        if(evt.getSource()==txtSize)
        {
            //this will assign the size of the array
            arraySize = Integer.parseInt(txtSize.getText());
            listElements.add("  Size of the Array: " + arraySize);
            listElements.add("===============================");
            arrayElements = new int [arraySize + 1];
            listElements.add("  Elements of the Array");
            listElements.add("===============================");
        }
       
        elements = Integer.parseInt(txtInput.getText());
        if(evt.getSource()==txtInput)
        {
            //this will determine if the array is full
            if(index==arrayElements.length-1)
            {
                listElements.add("No more space for new element.");
                bPrintSum.setEnabled(true);
            }

            else
            {   //this line of code will store the elements in the array with their indeces
                index++;
                arrayElements[index] = elements;
                listElements.add("--->  Element number " + index + ":   " + arrayElements[index]);
                temp = temp + arrayElements[index];
               
            }
            txtInput.selectAll();
            txtInput.requestFocus();
            bReset.setEnabled(true);
        }
               
        if(evt.getSource()==bPrintSum)
        {
          
            for (valueOfSum=0;valueOfSum<=temp;valueOfSum++)
            {
                num = arraySize * arraySize;
                for (index = 0; index < num; index++)
                {
                    subIndex = index;
                    possibleSum = 0;
                    ctr = 1;
                    while (subIndex > 0)
                    {
                        data = subIndex % 2;
                        if (data > 0)
                        possibleSum = possibleSum + arrayElements[ctr];
                        subIndex = subIndex / 2;
                        ctr++;
                    }
                    //this code will display the possible sums of all the elements in the array
                    if (possibleSum == valueOfSum)
                    listSums.add("                  " + valueOfSum);
                }
            }
            listSums.add("===============================");
            listSums.add("      There are " + index + " possible sums.");
            listSums.add("===============================");
            arraySize = 0;
            index = 0;
            bPrintSum.setEnabled(false);
        }
       
        if(evt.getSource()==bReset)
        {
            listElements.clear();
            listSums.clear();
            txtInput.setText("");
            txtSize.setText("");
            listElements.add("===============================");
            listElements.add("SIZE AND ELEMENTS OF THE ARRAY");
            listElements.add("===============================");
            listSums.add("===============================");
            listSums.add("  Possible SUMS of the ELEMENTS");
            listSums.add("===============================");
            bPrintSum.setEnabled(false);
            bReset.setEnabled(false);             
        }       
    }       
}

What are you waiting for, copy now, test, run and learn from it. Happy coding guys...