Updated: subsetSum

Question

Trying to write algorithm for subsetSum... It should find all possible subsets of a given vector, then find which ones add up to a target value. However, I keep getting nullpointerexceptions, and a few other errors. Can someone help me out? I'm in a tight spot, brain is hardly functioning. Much appreciated. Thanks.

java.lang.NullPointerException
at Sumation.subsetSum(Sumation.java:78)
at Sumation.main(Sumation.java:110)

Line 78 is line of first for loop in subsetSum method.

/* Ruben Martinez
 * CS 210 Data Structures
 * Program requires no paramters at main method call;
 * instead, a JOptionPane asks for the ints the user
 * wishes to search. These must be seperated by commas,
 * e.g. 50,40,30 or 35,45,55. Program then asks for a 
 * target int to find. Program searches for target
 * and returns combinations that add up to the target.
 */

import java.util.Vector; 
import javax.swing.*;

public class Sumation
{
    static int[] array;
    static int target;
    static Vector<Integer> subsets;
    static Vector<Integer> set;
    static Vector<Vector<Integer>> outer;

    public Sumation() {
        //insert integers into array
        String defineArray = (String)JOptionPane.showInputDialog(null,
                "Enter integers to search. Seperate by commas.", null);
        //splits string into array delimeted by commas
        String[] arrayString = defineArray.split(",");
        //creates int array of size of string array
        array = new int[arrayString.length];
        //adds ints from args[] to int array
        for (int i = 0; i < arrayString.length; i++) {
            array[i] = Integer.parseInt(arrayString[i]);
        }
        //enter integer to search for
        String targetString = (String)JOptionPane.showInputDialog(null,
                "What is your target integer?", null);
        //turns string to int
        target = Integer.parseInt(targetString);


        set = new Vector<Integer>();
        for (int n = 0; n < array.length; n++) {
            set.add(array[n]);
        }
    }

    private static Vector<Vector<Integer>> getSubsets(Vector<Integer> set) {
        Vector<Vector<Integer>> subsetCollection = new Vector<Vector<Integer>>();

        if (set.size() == 0) {
            subsetCollection.add(new Vector<Integer>());
        } else {
            Vector<Integer> reducedSet = new Vector<Integer>();
            reducedSet.addAll(set);

            int first = reducedSet.remove(0);
            Vector<Vector<Integer>> subsets = getSubsets(reducedSet);
            subsetCollection.addAll(subsets);

            subsets = getSubsets(reducedSet);

            for (Vector<Integer> subset : subsets) {
                subset.add(0, first);
            }

            subsetCollection.addAll(subsets);
        }

        return subsetCollection;
    }

    public static Vector<Vector<Integer>> subsetSum(Vector<Integer> subsets, int target) {
        //creates outer vector
        outer = new Vector<Vector<Integer>>();

        for (int k = 0; k < subsets.size(); k++) {
            //if k is the target, display
            if (array[k] == target) {
                //creates new inner vector for values that equal target
                Vector<Integer> inner = new Vector<Integer>();
                outer.add(inner);
                //add k to vector
                inner.add(array[k]);
            }
            for (int l =0; l < subsets.size(); l++) {
                int sum = subsets.elementAt(k);
                if (sum == target) {
                    //creates new inner vector for values that sum up to target
                    Vector<Integer> inner = new Vector<Integer>();
                    outer.add(inner);
                    //add l,k to vector
                    inner.add(array[l]);
                    inner.add(array[k]);
                }
                else {
                    System.out.print("");
                }
            }
        }
        //return combinations that add up to target in vector form
        return outer;
    }

    public static void main(String[] args) {
        //calls sumation constructor
        Sumation s = new Sumation();
        s.getSubsets(set);
        s.subsetSum(subsets, target);
        JOptionPane.showMessageDialog(null, "The combinations that equal to "+target+" are \n"+outer, "Vector", JOptionPane.INFORMATION_MESSAGE);
    }
}

Answer 1

How have you tried to analyse this?

If you have a debugger (i.e. IDE) on hand, it's very easy to analyse problems like this. Depending on your preference, you could

• Step through the program from start to finish
• Set a breakpoint on the line where the exception's thrown
• Set a breakpoint for NullPointerExceptions

and in all cases you'd easily see what the state of the variables/fields are all all points. If you get into an unexpected state it's easy to rewind or rerun the program to see the results of previous calculations and watch for where it deviates from your expectations.

Even if you don't have a debugger to hand, you could put println statements in every so often (and definitely just before the exception line) so as to see what the values are - a poor man's debugger.

But seriously, get a real debugger set up if you're going to be doing any non-trivial Java dev. If will take 5-20 minutes and will save you more than that the first time you have to investigate a problem like this.

---

Anyway, the problem is caused by the fact that you never assign anything to the subsets field, so it's null when you pass it into subsetSum in main.

This might be because the subset local variable within the getSubsets method shadows it - if you were expecting that method to modify the field then you'd be mistaken. But then, that would be bad practice anyway (IMHO), as changing state like that in a recursive method would be very easy to get wrong, and even if correct would make it hard to reason about the class at any point (as you'd need to know what state it was in). Assigning results to fields is a common beginner's mistake (possibly because it feels more object-oriented?), when the better option is to have a method return its result, which will then usually be stored in a local variable.

So the main method should assign the result of the getSubsets call to a local variable, and then pass that into the subsetSum method.

(I notice that the types aren't entirely compatible - are you sure that the argument to subsetSum shouldn't be a Vector<Vector<Integer>> too? At the moment it looks like you could only pass in a single subset. But that's a different matter.)