title: Possible combinations of size a whose sum is equal to b
body: <p>Problem: Given a number 'a' and number 'b'. Find all the combinations whose size is 'a' and sum of the numbers in the combination should be equal to 'b'.</p>
  
  <p>Example: a = 3, b = 5. For simplicity consider only whole numbers. 
  Combinations - { (0, 0, 5}, (1, 1, 3), (1, 2, 2), (0, 1, 4), (0, 2, 3)}. 
  {1, 3, 1} is not a valid combination because (1, 1, 3) is already in the solution. </p>
  
  <p>Here is my solution.</p>
  
  <pre><code>    public void CombinationsMain()
      {
          Console.Write("Enter the target sum: ");
          string tsum = Console.ReadLine();
          Console.Write("Enter the number of combinations: ");
  
          string combination = Console.ReadLine();
          int targetsum;
          Int32.TryParse(tsum, out targetsum);
          int m;
          Int32.TryParse(combination, out m);
          int[] arr = new int[m];
          CombinationsUtil(targetsum, 0, arr);
          Console.ReadLine();
      }
  
      public void CombinationsUtil(int targetsum, int index, int[] arr)
      {
          //check if the length of the current index is same as arr length and sum 
          //before printing the combination
          //SumofArrayElements ignores the combination like {0 0 5 0} { 0 5 0 0} and will print only { 0 0 0 5}
          if (index == arr.Length &amp;&amp; SumOfArrayElements(arr, targetsum))
          {
              for (int i = 0; i &lt; arr.Length; i++)
                  Console.Write(arr[i]);
              Console.WriteLine();
          }
  
          for (int i = 0; i &lt;= targetsum &amp;&amp; index &lt; arr.Length; i++)
          {
              arr[index] = i;
              CombinationsUtil(targetsum, index + 1, arr);
          }
      }
  
      //returns true or false comparing sum of elements of array and given target sum
      public bool SumOfArrayElements(int[] arr, int targetsum)
      {
  
          int sum = 0;
          for (int i = 0; i &lt; arr.Length; i++)
          {
              if (i &lt; arr.Length-1 &amp;&amp; arr[i] &gt; arr[i + 1])
                  return false;
              sum += arr[i];
          }
          return sum == targetsum;
      }
  </code></pre>
  
  <p>Time complexity is O(n^m) (n here is targetsum). Can it be optimized any further or is this the best I can do? Thanks for your inputs.</p>