title: Generating the partitions of a number
body: <p>I needed an algorithm to generate all possible partitions of a positive number, and I came up with one (posted as an answer), but it's exponential time.</p>
  
  <p>The algorithm should return all the possible ways a number can be expressed as the sum of positive numbers less than or equal to itself. So for example for the number <strong>5</strong>, the result would be:</p>
  
  <ul>
  <li>5</li>
  <li>4+1</li>
  <li>3+2</li>
  <li>3+1+1</li>
  <li>2+2+1</li>
  <li>2+1+1+1</li>
  <li>1+1+1+1+1</li>
  </ul>
  
  <p>So my question is: is there a more efficient algorithm for this?</p>
  
  <p><strong>EDIT:</strong> Question was titled <em>"Sum decomposition of a number"</em>, since I didn't really know what this was called. <a href="https://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number#400810">ShreevatsaR pointed out</a> that they were called "partitions," so I edited the question title accordingly.</p>