Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote -1 down vote favorite

What is wrong with this code? It should return the power set of a given set.

static public <T> ArrayList< ArrayList<T> > powerSet(ArrayList<T> inputSet){
  ArrayList< ArrayList<T> > power = new ArrayList< ArrayList<T> >();

  if(inputSet.isEmpty()){        
    power.add(new ArrayList<T>());
    return power;
  }

  T element = inputSet.remove(0);
  ArrayList< ArrayList<T> > partial = powerSet(inputSet);
  power.addAll(partial);
  for(ArrayList<T> sub : partial){
    sub.add(element);
    power.add(sub);
  }
  return power;
}
share|improve this question
This site is about getting feedback for working code. It's not a place for other people to debug your code. – sepp2k♦ Dec 29 '12 at 11:44
Sorry, was just trying to learn. Don't worry, I'll go elsewhere. – Brainstorming Mar 11 at 22:41

closed as off topic by Glenn Rogers, Corbin, Brian Reichle, seand, Jeff Vanzella Dec 29 '12 at 4:50

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

1 Answer

up vote 1 down vote accepted

First of all, ArrayList is not a set, you'd better use Set, but it really depends on your requirements.

Also, you should use specific classes only when you call their specific methods, otherwise use interfaces. See Why are interfaces useful?

The problem with you code is that in for loop you add element to a list from power, but should create a new list. This should work:

static public <T> List<List<T>> powerSet(List<T> inputSet) {
    List<List<T>> resultPowerSet = new ArrayList<List<T>>();

    if (inputSet.isEmpty()) {
        resultPowerSet.add(new ArrayList<T>());
        return resultPowerSet;
    }

    T headElement = inputSet.remove(0);
    List<List<T>> tailPowerSet = powerSet(inputSet);
    resultPowerSet.addAll(tailPowerSet);
    for (List<T> tailSet : tailPowerSet) {
        List<T> headSet = new ArrayList<T>(tailSet);
        headSet.add(headElement);
        resultPowerSet.add(headSet);
    }
    return resultPowerSet;
}
share|improve this answer
3  
He should also be using the interfaces (eg, Set) instead of using the actual classes. – Clockwork-Muse Dec 28 '12 at 22:05

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