title: Creating all possible combinations sorted by sum
body: <p>Given an arbitrary set of numbers <code>S = {1..n}</code> and size <code>k</code>, I need to print all possible combinations of size <code>k</code> ordered by the sum of the combinations.</p>
  <p>Let's say <code>S = {1, 2, 3, 4, 5}</code> and <code>k = 3</code>, a sample output would be:</p>
  <pre><code>1 2 3 = 6
  1 2 4 = 7
  1 2 5 = 8
  1 3 4 = 8
  1 3 5 = 9
  2 3 4 = 9
  2 3 5 = 10
  1 4 5 = 10
  2 4 5 = 11
  3 4 5 = 12
  </code></pre>
  <p>The first idea that came to my mind is to sort <code>S</code> (if not already sorted) and then perform a BFS search, having a queue of combinations sorted by sum. This is because I want to generate the next combination <strong>only if requested</strong> (iterator like). But this seems like an overkill and I think that there should be an easier solution. How can this be solved?</p>
  <p><strong>Edit:</strong></p>
  <p>This is my original idea:</p>
  <pre><code>1. Sort S
  2. Pick the first k numbers and add them to the queue as a single node (because this is the combination with the smallest sum)
  3. While the queue is not empty - pop the first node, output it, and generate successors.
  
  Generating successors:
  1. Start with the first number in the node. Make a copy of a node. Find the smallest unselected value that is &gt; than the number, and assign this value.
  2. Verify that this node hasn't been seen and calculate the sum.
  3. Add the node to the queue.
  4. Repeat 1-3 for all of the remaining numbers in the node.
  </code></pre>
  <p><strong>Example:</strong></p>
  <pre><code>Queue q = { {1, 2, 3} = 6 }
  Pop front, output
      1 2 3 = 6
  Generate {4, 2, 3} = 9, {1, 4, 3} = 8, {1, 2, 4} = 7
  Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4} }
  
  Queue q = { {1, 2, 4} = 7, {1, 4, 3} = 8, {4, 2, 3} = 9 }
  Pop front, output
      1 2 3 = 6
      1 2 4 = 7
  Generate {3, 2, 4} = 9 (seen - discard), {1, 3, 4} = 8 (seen - discard), {1, 2, 5} = 8 }
  Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4}, {1, 2, 5} }
  
  Queue q = { {1, 2, 5} = 8, {1, 4, 3} = 8, {4, 2, 3} = 9 }
  Pop front, output
      1 2 3 = 6
      1 2 4 = 7
      1 2 5 = 8
  Generate {3, 2, 5} = 10, {1, 3, 5} = 9
  Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4}, {1, 2, 5}, {3, 2, 5}, {1, 3, 5} }
  
  Queue q = { {1, 4, 3} = 8, {1, 5, 3} = 9, {1, 3, 5} = 9,  {3, 2, 5} = 10, {1, 4, 5} = 10, {4, 2, 5} = 11 }
  ...
  ...
  </code></pre>