title: Optimal way to obtain get Powerset of a List (recursively)
body: <p>To the get the power set of a list, I implemented the following:</p>
  
  <pre><code>public static ArrayList&lt;ArrayList&lt;Integer&gt;&gt; getAllSubsets(ArrayList&lt;Integer&gt; set, int index, ArrayList&lt;Integer&gt; subset){
      ArrayList&lt;ArrayList&lt;Integer&gt;&gt; subsets = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
  
      if(index == set.size()){
          subsets.add(new ArrayList&lt;Integer&gt;(subset));
          return subsets;
      }
  
      subsets.addAll(getAllSubsets(set, index + 1, subset));
      subset.add(set.get(index));
      subsets.addAll(getAllSubsets(set, index + 1, subset));
      subset.remove(subset.size()-1);
      return subsets;
  }
  </code></pre>
  
  <p>Is this the optimal way to get the power set of a list using recursion?   I've see tons of different ways on how to implement this on the internet but they seem do more copying (use of new) than mine.  </p>
  
  <p>For instance, this <a href="https://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java">StackOverlow post</a> came up on my Google searches but his  implementation (Joao Silva) uses a lot of copying and seems non-optimal.  However, I've seen his implementation quite often which puzzles me.  Is that implementation better than the one I'm using (other that the fact he is using generics of course) ?</p>
  
  <p>His code:</p>
  
  <pre><code>public static &lt;T&gt; Set&lt;Set&lt;T&gt;&gt; powerSet(Set&lt;T&gt; originalSet) {
      Set&lt;Set&lt;T&gt;&gt; sets = new HashSet&lt;Set&lt;T&gt;&gt;();
      if (originalSet.isEmpty()) {
          sets.add(new HashSet&lt;T&gt;());
          return sets;
      }
      List&lt;T&gt; list = new ArrayList&lt;T&gt;(originalSet);
      T head = list.get(0);
      Set&lt;T&gt; rest = new HashSet&lt;T&gt;(list.subList(1, list.size())); 
      for (Set&lt;T&gt; set : powerSet(rest)) {
          Set&lt;T&gt; newSet = new HashSet&lt;T&gt;();
          newSet.add(head);
          newSet.addAll(set);
          sets.add(newSet);
          sets.add(set);
      }       
      return sets;
  }
  </code></pre>