Find all combinations of 1 and 2 that add up to N

Question

Say I have a function like this. I need to know all the combinations of 1 and 2 that will add up to N. Is there a better way to write this that would perform better for a large integer such as N = 1200 or 12000?

public static int Combos(int n)
{
    if (n < 3)
    {
        return n;
    }
    else
    {
        return Combos(n - 1) + Combos(n - 2);
    }
}

Answer 1

Find all combinations of 1 and 2 that add up to N

So, you need combinations and not permutations.

Let's see some examples-

• 1 = {1}
• 2 = {1,1}, {2}
• 3 = {1,1,1}, {1,2} (or {2,1} , both are same).
• 4 = {1,1,1,1}, {1,2,1}, {2,2}
• 5 = {1,1,1,1,1}, {1,2,1,1}, {2,2,1}
• 6 = {1,1,1,1,1,1}, { 1,2,1,1,1} , {2,2,1,1} , {2,2,2}
• 7 = {1,1,1,1,1,1,1}, { 1,2,1,1,1,1} , {2,2,1,1,1} , {2,2,2,1}

If you observe, it looks like this-

• 1 = 1
• 2 = 2
• 3 = 2
• 4 = 3
• 5 = 3
• 6 = 4
• 7 = 4
• 8 = 5

You can solve this in O(1) time and O(1) space like below-

public static int Combos(int n){
    return n / 2 + 1;
}   

Note #1: If you need values also, then it will take a bit more effort, but with your code it looks like you only want to find no. of ways.

Note #2: Finding the actual values would also not take much effort if you notice. You don't need to remember previous results at all.

Answer 2

The algorithm in your sample calculates the number of permutations, not combinations, of 1's and 2's that add up to a number N, so I'll answer a way to find the answer to that faster.

Firstly, let's try running it for the first few numbers

> Enumerable.Range(1, 20).Select(Combos).ToList()
List<int>(20) { 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 }

This sequence is actually a well known sequence, it's the sequence of fibonacci numbers!

The code that you posted is the typical example of the naive recursive implementation of calculating fibonacci numbers, and is an example that is often used when teaching about dynamic programming.

There are many resources online about how to implement a faster approach, but one such way is to build the value from the bottom up rather than the top down such as the following:

int Combos(int n)
{
    if (n < 3)
        return n;
    int previous = 2;
    int previous2 = 1;
    for (int i = 3; i <= n; i++)
    {
        int newValue = previous + previous2;
        previous2 = previous;
        previous = newValue;
    }
    return previous;
}

Answer 3

Number of permutations optimized:

static void Main(string[] args)
{
   var result = Combos(1200);
}

static Dictionary<long, long> cache = new Dictionary<long, long>();
public static long Combos(long n)
{           
   if (n < 3)
   {
      return n;
   }
   else
   {
      if (!cache.TryGetValue(n - 1, out long combos1))
      {
          combos1 = Combos(n - 1);
          cache.Add(n - 1, combos1);
      }
      if (!cache.TryGetValue(n - 2, out long combos2))
      {
          combos2 = Combos(n - 2);
          cache.Add(n - 2, combos2);
      }
      return combos1 + combos2;
   }
}

If you need combinations then you need to ask separate question to optimize the following code (from the following source):

static void Main(string[] args)
        {
            FindCombinations(20);
            Console.ReadKey();
        }
        //IEnumerable<IEnumerable<int>>
        static void FindCombinationsUtil(int[] arr, int index,
                                 int num, int reducedNum)
        {
            // Base condition 
            if (reducedNum < 0)
                return;

            // If combination is  
            // found, print it 
            if (reducedNum == 0)
            {
                for (int i = 0; i < index; i++)
                    Console.Write(arr[i] + " ");
                Console.WriteLine();
                return;
                //yield return arr;                                
            }

            // Find the previous number  
            // stored in arr[]. It helps  
            // in maintaining increasing  
            // order 
            int prev = (index == 0) ?
                                  1 : arr[index - 1];

            // note loop starts from  
            // previous number i.e. at 
            // array location index - 1 
            for (int k = prev; k <= num; k++)
            {
                // next element of 
                // array is k 
                arr[index] = k;

                // call recursively with 
                // reduced number 
                FindCombinationsUtil(arr, index + 1, num,
                                         reducedNum - k);
            }
        }

        /* Function to find out all  
        combinations of positive  
        numbers that add upto given 
        number. It uses findCombinationsUtil() */
        static void FindCombinations(int n)
        {
            // array to store the combinations 
            // It can contain max n elements 
            int[] array = new int[n];

            // find all combinations 
            FindCombinationsUtil(array, 0, 2, n);            
        }