title: generate all partitions of a set
body: <p>For a set of the form <code>A =  {1, 2, 3, ..., n}</code>. It is called partition of the set <code>A</code>, a set of <code>k&lt;=n</code> elements which respect the following theorems:</p>
  <p>a) the union of all the partitions of <code>A</code> is <code>A</code></p>
  <p>b) the intersection of 2 partitions of <code>A</code> is the empty set (they can't share the same elements).</p>
  <p>For example. <code>A = {1, 2,... n}</code> We have the partitions:</p>
  <pre class="lang-none prettyprint-override"><code>{1, 2, 3}
  {1, 2} {3}
  {1, 3} {2}
  {2, 3} {1}
  {1} {2} {3}
  </code></pre>
  <p>These theoretical concepts are presented in my algorithms textbook (by the way, this subchapter is part of the &quot;Backtracking&quot; chapter). I am supposed to find an algorithm to generate all the partitions of a given set. I was struggling with this problem all the day and I couldn't find a solution. Can you explain me how does this algorithm work? Also, can you give me a pseudo-code sketch of the algorithm?</p>