Count number of ways to cover a distance

Given a distance ‘dist’, count total number of ways to cover the distance with 1, 2 and 3 steps.
Examples:
Input: n = 3
Output: 4
Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step

Input: n = 4
Output: 7

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        public static int counter = 0;

        static void Main(string[] args)
        {
            int distance = 4;
            int[] stepArray = { 1, 2, 3 };
            RecursiveSum(distance, stepArray, 0, "");
            Console.WriteLine("Total number of ways = " + counter);
        }
       
        public static void RecursiveSum(int distance, int[] stepArray, int sum, string str)
        {
            if(sum > distance)
            {
                return;
            }
            else if(sum == distance && str.Length != 0)
            {
                counter++;
                Console.WriteLine(counter + ". " + str);
            }
            else
            {
                for(int i = 0; i < stepArray.Length; i++)
                {
                    if(str == "")
                    {
                        RecursiveSum(distance, stepArray, sum + stepArray[i], str + stepArray[i].ToString());
                    }
                    else
                    {
                        RecursiveSum(distance, stepArray, sum + stepArray[i], str + ", " + stepArray[i].ToString());
                    }
                }
            }
        }
    }
}

Output
=======
1. 1, 1, 1, 1
2. 1, 1, 2
3. 1, 2, 1
4. 1, 3
5. 2, 1, 1
6. 2, 2
7. 3, 1
Total number of ways = 7
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s