1
\$\begingroup\$
  1. I am concerned about creating too many objects in my code.

  2. Am I using duplicate code? Can I cut down on the number of lines of code?

Note: I only want to use recursion to solve this. Any suggestions on the design of the program and naming convention used here are appreciated.

import java.util.ArrayList;

class Subsets {
    public static void main(String[] args) {
        ArrayList<Integer> superSet = new ArrayList<Integer>();
        superSet.add(1);
        superSet.add(2);
        superSet.add(3);
        superSet.add(4);
        ArrayList<ArrayList<Integer>> lists = Subsets.getSubsets(superSet);
        System.out.println("final set ==> " + lists);
    }

    static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> SubList) {
        if (SubList.size() > 0) {
            ArrayList<ArrayList<Integer>> list = addToList(SubList.remove(0),
                    SubList);
            return list;
        } else {
            ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            list.add(SubList);
            return list;
        }
    }

    private static ArrayList<ArrayList<Integer>> addToList(
            Integer firstElement, ArrayList<Integer> SubList) {
        ArrayList<ArrayList<Integer>> listOfLists = getSubsets(SubList);
        ArrayList<ArrayList<Integer>> superList = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> iList : listOfLists) {
            superList.add(new ArrayList<Integer>(iList));
            iList.add(firstElement);
            superList.add(new ArrayList<Integer>(iList));
        }
        return superList;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ You may try and operate on the original list's .toArray(): this way you will have no need to create sublists of your original list \$\endgroup\$
    – fge
    Jun 29 '13 at 14:22
2
\$\begingroup\$

You can combine your two methods in just one method, making the whole process much easier to understand due to less "jumping around".

static <T> List<List<T>> getSublists(List<T> list) {
    if (list.isEmpty()) {
        // if empty, return just that empty list
        return Collections.singletonList(list);
    } else {
        List<List<T>> sublists = new ArrayList<List<T>>();
        T first = list.get(0);
        // for each sublist starting at second element...
        for (List<T> sublist : getSublists(list.subList(1, list.size()))) {
            //... add that sublist with and without the first element
            // (two lines more, but this preserves the original order)
            List<T> sublistWithFirst= new ArrayList<T>();
            sublistWithFirst.add(first);
            sublistWithFirst.addAll(sublist);
            sublists.add(sublist);
            sublists.add(sublistWithFirst);
        }
        return sublists;
    }
}

Some more points:

  • I'd recommend using the more generic List whenever possible.
  • Also, no need to restrict the method to lists of integers.
  • That code definitely deserves some comments.
  • You are actually returning sub-lists; name your methods accordingly.
  • Note that by calling remove on the input list, you are modifying the original list!
\$\endgroup\$
1
\$\begingroup\$

My only input is about the getSubsets() method. I'd change it to:

   static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> SubList) {
        ArrayList<ArrayList<Integer>> list; //You're gonna make a list either way.
        if (SubList.size() > 0) {
            list = addToList(SubList.remove(0), SubList);
        } else {
            list = new ArrayList<ArrayList<Integer>>();
            list.add(SubList);
        }
        return list;//You only need one return statement
    }

I generally don't like multiple return statements, because each one represents a path through which your method can just end abruptly, even if there's more code. But this is something up for debate (see this).

You also make a list object in both cases, so why not just make it upfront and make things more readable?

Also, I would douse that code in comments. And finally, I'd probably just make my own class instead of dealing with that horrible syntax.

This saves you from typos, too:

class ArrayListHolder extends ArrayList<ArrayList<Integer>>{
      //This can be an inner class.   
}

  //For example, your addToList method will look like:

private static ArrayListHolder addToList(
         Integer firstElement, ArrayList<Integer> SubList) {
    ArrayListHolder listOfLists = getSubsets(SubList);
    ArrayListHolder superList = new ArrayListHolder();
    for (ArrayList<Integer> iList : listOfLists) {
        superList.add(new ArrayList<Integer>(iList));
        iList.add(firstElement);
        superList.add(new ArrayList<Integer>(iList));
    }
    return superList;
}

That's just purely my opinion on what you should do. No real reason other than readability, and my hatred for the ArrayList syntax. Otherwise, good job.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.