title: List all possible combinations of k integers between 1...n (n choose k)
body: <p>Out of no particular reason I decided to look for an algorithm that produces all possible choices of k integers between 1...n, where the order amongst the k integer doesn't matter (the n choose k thingy). </p>
  
  <p>From the exact same reason, which is no reason at all, I also implemented it in C#. My question is:</p>
  
  <p><em>Do you see any mistake in my algorithm or code? And, more importantly, <strong>can you suggest a better algorithm?</em></strong></p>
  
  <p>Please pay more attention to the algorithm than the code itself. It's not the prettiest code I've ever written, although do tell if you see an error.</p>
  
  <p><strong>EDIT:</strong> Alogirthm explained - <br/></p>
  
  <ul>
  <li>We hold k indices.</li>
  <li>This creates k nested <em>for</em> loops, where loop i's index is indices[i]. </li>
  <li>It simulates k <em>for</em> loops where indices[i+1] belongs to a loop nested within the loop of indices[i].</li>
  <li>indices[i] runs from indices[i - 1] + 1 to n - k + i + 1.</li>
  </ul>
  
  <p>CODE:</p>
  
  <pre><code>public class AllPossibleCombination
  {
      int n, k;
      int[] indices;
      List&lt;int[]&gt; combinations = null;
  
      public AllPossibleCombination(int n_, int k_)
      {
          if (n_ &lt;= 0)
          {
              throw new ArgumentException("n_ must be in N+");
          }
          if (k_ &lt;= 0)
          {
              throw new ArgumentException("k_ must be in N+");
          }
          if (k_ &gt; n_)
          {
              throw new ArgumentException("k_ can be at most n_");
          }
  
          n = n_;
          k = k_;
          indices = new int[k];
          indices[0] = 1;
      }
  
      /// &lt;summary&gt;
      /// Returns all possible k combination of 0..n-1
      /// &lt;/summary&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      public List&lt;int[]&gt; GetCombinations()
      {
          if (combinations == null)
          {
              combinations = new List&lt;int[]&gt;();
              Iterate(0);
          }
          return combinations;
      }
  
      private void Iterate(int ii)
      {
          //
          // Initialize
          //
          if (ii &gt; 0)
          {
              indices[ii] = indices[ii - 1] + 1;
          }
  
          for (; indices[ii] &lt;= (n - k + ii + 1); indices[ii]++)
          {
              if (ii &lt; k - 1)
              {
                  Iterate(ii + 1);
              }
              else
              {
                  int[] combination = new int[k];
                  indices.CopyTo(combination, 0);
                  combinations.Add(combination);
              }
          }
      }
  }
  </code></pre>
  
  <p>I apologize for the long question, it might be fit for a blog post, but I do want the community's opinion here.</p>
  
  <p>Thanks, <br/>
  Asaf</p>