title: Get all possible partitions of a set
body: <p>In Java I have a set where I want to obtain all possible combinations of subsets which their union make the main set. (partitioning a set)
  for example, given:</p>
  
  <pre><code>set={1,2,3}
  </code></pre>
  
  <p>the result should be:</p>
  
  <pre><code>{ {{1,2,3}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}}
  </code></pre>
  
  <p>the number of possible partition of a set of <code>n</code> elements is <code>B(n)</code> known as <a href="https://en.wikipedia.org/wiki/Bell_number" rel="nofollow noreferrer">Bell number</a>.</p>
  
  <p>The code so far:</p>
  
  <pre><code>public static &lt;T&gt; Set&lt;Set&lt;T&gt;&gt; powerSet(Set&lt;T&gt; myset) {
          Set&lt;Set&lt;T&gt;&gt; pset = new HashSet&lt;Set&lt;T&gt;&gt;();
          if (myset.isEmpty()) {
              pset.add(new HashSet&lt;T&gt;());
              return pset;
          }
          List&lt;T&gt; list = new ArrayList&lt;T&gt;(myset);
          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);
              pset.add(newSet);
              pset.add(set); 
          }
  
          return pset;
      }
  </code></pre>
  
  <p>which outputs the powerset of the the array :</p>
  
  <pre><code>[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
  </code></pre>