THE PROBLEM STATEMENT

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the list of unique ways you can climb the staircase. The order of the steps matters.

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Example 1

Input: staircaseSteps = 3
Input: possibleSteps = { 1, 2 }
Output: [[1, 1, 1], [1, 2], [2, 1]]

Example 2

Input: staircaseSteps = 4
Input: possibleSteps = { 1, 2 }
Output: [[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2]]

Example 3

Input: staircaseSteps = 3
Input: possibleSteps = { 1, 2, 3 }
Output: [[1, 1, 1], [1, 2], [2, 1], [3]]

Example 4

Input: staircaseSteps = 4
Input: possibleSteps = { 1, 2, 3 }
Output: [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]

SOLUTION?

How do you approach a problem? Sometimes there is a problem in our approach to a problem. We get stuck into solving it in one way and therefore ignore other possibilities.

So make sure you try to see both sides of a coin. Every story has multiple sides. That’s why we have two lawyers for a case in court

So, When you see such problems what comes into your mind? A picture perhaps? Some thing like following:

A tree

This visualization tells you the answer when you have 3 stairs and possible steps are 1 or 2 steps.

You can see the combinations are three. And you can track them. So shall we use tree structure to solve this problem? Or WAIT!

Can you put this image as a method calling sequence or some thing. Well, yes. You can use RECURSION!

Lets get started then. The method I have created is following:

public static List<int[]> GetCombinations(int staircaseSteps, int[] possibleSteps, List<int> stepsHistory, List<int[]> combinations)
{
	if (staircaseSteps == 0)
	{
		combinations.Add(stepsHistory.ToArray());
		return combinations;
	}

	foreach (int step in possibleSteps)
	{
        //Skip step if bigger than remaining stairs
		if (staircaseSteps - step >= 0)
		{
			List<int> steps = stepsHistory.Select(x => x).ToList();
			steps.Add(step);
			GetCombinations(staircaseSteps - step, possibleSteps, steps, combinations);
		}
	}
	return combinations;
}

Lets try this code now

public static void Main(string[] args)
{
	int staircaseSteps = 5;
	int[] possibleSteps = new int[] { 1, 3, 5 };

	List<int[]> comb = GetCombinations(staircaseSteps, possibleSteps, new List<int>(), new List<int[]>());

	Console.WriteLine($"Combination Length: {comb.Count}");
    //Print the combinations
	PrintCombinations(comb);

	Console.ReadKey();
}

And this method to print the combinations

public static void PrintCombinations(List<int[]> combinations)
{
	foreach (int[] c in combinations)
	{
		foreach (int s in c)
		{
			Console.Write(s);
		}
		Console.WriteLine();
	}
}

As you increase the number of staircase steps and possible steps the graph will get bigger and bigger and you might have to restart you computer to get it back to its senses.

The method PrintCombinations itself will take alot of time since it is a nested loop with bigO n square.

So what should we do about that? Threads perhaps? or Async programming?

Well, I tried Async method and it turned out to be slower than the synchronous one. I won’t go into details of that as of yet. But lets take a look at it.

public async static Task<List<int[]>> GetCombinationsAsync(int staircaseSteps, int[] possibleSteps, List<int> stepsHistory, List<int[]> combinations)
{
	if (staircaseSteps == 0)
	{
		combinations.Add(stepsHistory.ToArray());
		return combinations;
	}

	List<Task> tasks = new List<Task>();
	foreach(int step in possibleSteps)
	{
		if(staircaseSteps - step >= 0)
		{
			List<int> steps = stepsHistory.Select(x => x).ToList();
			steps.Add(step);
			tasks.Add(GetCombinationsAsync(staircaseSteps - step, possibleSteps, steps, combinations));
		}
	}
	Task.WaitAll(tasks.ToArray());
	return combinations;
}

I am looking forward to hearing from you guys in comment section below.

Thanks for stopping by! Happy coding!