CareerCup

public class AllPossibleSteps {
    public static void main(String[] args) {
        int steps = 4;
        printAllpossibleSteps("",steps);
    }

    public static void printAllpossibleSteps(String path, int steps) {
        if(steps > 0) {
            printAllpossibleSteps(path+" 1",steps-1);
            printAllpossibleSteps(path+" 2",steps-2);
        } else if(steps == 0) {
            System.out.println(path);
        }
    }
}

Just need a recursive function that calls itself with 1 and 2 stairs (if there are enough remaining). Below, my recursive function is called "step", and I also have a "stairs" function which calls it to satisfy the interface.

#include <vector>
#include <string>

using namespace std;

void step(string currentSolution, int remaining, vector<string> &allSolutions)
{
	if (remaining == 0)
	{
		allSolutions.push_back(currentSolution);
		return;
	}

	step(currentSolution + "1", remaining - 1, allSolutions);
	if (remaining > 1)
	{
		step(currentSolution + "2", remaining - 2, allSolutions);
	}
}

vector<string> stairs(int steps)
{
	vector<string> allSolutions;
	step(string(""), steps, allSolutions);
	return allSolutions;
}

Recursive approach will calculate same solutions multiple times. Consider using DP.

public HashSet<String> stairs(int n) {

		ArrayList<HashSet<String>> prevPaths = new ArrayList<HashSet<String>>();

		HashSet<String> st1 = new HashSet<String>();
		st1.add("1");
		if(n == 1) return st1;
		prevPaths.add(st1);

		HashSet<String> st2 = new HashSet<String>();
		st2.add("11");
		st2.add("2");
		if(n == 2) return st2;
		prevPaths.add(st2);

		for (int i = 3; i <= n; i++) {
			HashSet<String> sti = new HashSet<String>();

			HashSet<String> sti_1 = prevPaths.get(1);
			for(String subPath : sti_1) {
				sti.add("1" + subPath);
				sti.add(subPath + "1");
			}
			HashSet<String> sti_2 = prevPaths.get(0);
			for(String subPath : sti_2) {
				sti.add("2" + subPath);
				sti.add(subPath + "2");
			}

			prevPaths.add(0, prevPaths.get(1));
			prevPaths.add(1, sti);
		}

		return prevPaths.get(1);
	}

public class Solution {
public int climbStairs(int n) {
if(n<=3){
return n;
}
int preOne=1,preTwo=2,sum=0;
for(int i=2;i<n;i++){
sum = preOne+preTwo;
preOne = preTwo;
preTwo = sum;

}
return sum;
}
}

{
public class Solution {
public int climbStairs(int n) {
if(n<=3){
return n;
}
int preOne=1,preTwo=2,sum=0;
for(int i=2;i<n;i++){
sum = preOne+preTwo;
preOne = preTwo;
preTwo = sum;

}
return sum;
}
}


}

(function(){
    var arr = [1,2];
    var sol = [];
    var N = 3;
    
    stair(N,arr,sol);
})()

function stair(N, arr, sol){
    if(N<0){
        return;
    }
    if(N===0){
        console.log(sol);
        return;
    }else{
        for(var i = 0; i < arr.length; i++){
            sol.push(arr[i]);
            stair(N-arr[i],arr,sol);
            sol.pop(arr[i]);
        }
    }
}

# solution in Python 2.7, written by Mahmoud Assi
def stairs (n):
    array = []
    if (n == 1):
        array.append([1])
    elif (n == 2):
        tempArray = stairs(n-1)
        for temp in tempArray:
            array.append([1]+ temp)
        array.append([2])
    else:
        tempArray = stairs(n-1)
        for temp in tempArray:
            array.append([1]+ temp)

        tempArray = stairs(n-2)
        for temp in tempArray:
            array.append([2]+ temp)
            
    return array

result = stairs(6)

for array in result:
    print (''.join(str(x) for x in array ) )

void printSteps(int n, int remaining, vector<int> v)
{
	if(remaining < 0)
		return;
	if(remaining==0)
		{
			for(int i=0; i< v.size(); i++)
			{
				cout << v.at(i) <"\t";
				
			}
		cout<<endl;
		v.clear();
		return;
		}
	v.push_back(1);
	printSteps(n, remaining-1, v);
	v.pop_back();
	v.push_back(2);
	printSteps(n, remaining-2, v);
	v.pop_back();
}

void printSteps(int n, int remaining, vector<int> v)
{
	if(remaining < 0)
		return;
	if(remaining==0)
		{
			for(int i=0; i< v.size(); i++)
			{
				cout << v.at(i) <"\t";
				
			}
		cout<<endl;
		v.clear();
		return;
		}
	v.push_back(1);
	printSteps(n, remaining-1, v);
	v.pop_back();
	v.push_back(2);
	printSteps(n, remaining-2, v);
	v.pop_back();
}

Logic: just recurse with the steps 1 and 2 and when it reaches 0 then it means we are on top and print the result.

#include <stdio.h>

int a[100];
int i=0;

void foo(int size, int i)
{
	if (size < 0)
		return;
	if (size == 0) {
		int j;
		for (j=0;j<i;j++)
			printf("%d", a[j]);
		printf("\n");
		return;
	}
	a[i] = 1;
	foo(size - 1, i+1);
	a[i] = 2;
	foo(size - 2, i+1);
}

int main(void) {
	foo(4, 0);
	return 0;
}

void stairs(int n, string s /*default to "" */) {
	if(n == 0)
		cout<<s<<endl;
	if(n == 1)
		cout<<s+"1"<endl;

	stairs(n-1, s + "1");
	stairs(n-2, s + "2");
}

Vector<String> stairs(int n) {
	HashMap<Integer, Vector<String>> table = new HashMap<Integer, Vector<String>>();
	
	Vector<String> ret = new Vector<String>();
	if (n <= 0) {
		return ret;
	}
	
	if (n == 1) {
		String line = "1";
		ret.add(line);
		table.put(1, ret);
		return ret;
	}
	
	if (n == 2) {
		String line1 = "11";
		ret.add(line1);
		
		String line2 = "2";
		ret.add(line2);
		
		table.put(2, ret);
		return ret;
	}
	
	
	Vector<String> subRet1 = table.get(n - 1);
	if (subRet1 == null) {
		subRet1 = stairs(n - 1);
	}
	for (int i = 0; i < subRet1.size(); i++) {
		ret.add("1" + subRet1.get(i));
	}
	
	Vector<String> subRet2 = table.get(n - 2);
	if (subRet2 == null) {
		subRet2 = stairs(n - 2);
	}
	for (int i = 0; i < subRet2.size(); i++) {
		ret.add("2" + subRet2.get(i));
	}
		
	return ret;
}

public int getMaxSum(int [] arr,int k,int sum){
		
		if(k==2||k==1||k==0)
			return sum+arr[0]+Math.max(arr[1], arr[2]);
		
		else{
			
			
			return sum +arr[k] + Math.max(getMaxSum(arr, k-1,sum), getMaxSum(arr, k-2,sum));
			//return sum;
		}

Includes both recursive as well as iternative solution

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int steps = 4;
		int totRec = stepRec(steps);
		System.out.println(totRec);
		
		int totIte = stepIte(steps);
		System.out.println(totIte);
	}
	
	public static int stepIte(int steps){
		if(steps == 1)
			return 1;
		if(steps == 2)
			return 2;
		
		int[] arr = {1,2};
		int curr = 2;
		while(curr < steps){
			int total = arr[0]+arr[1];
			arr[0] = arr[1];
			arr[1] = total;
			curr++;
		}
		return arr[1];
	}
	
	public static int stepRec(int steps){
		if(steps == 1){
			return 1;
		}
		 if (steps == 2){
			return 2;
		}
		
		else
			return stepRec(steps-1) + stepRec(steps-2);
	}
}

// StepsCalculator1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <cassert>

void CalculateSteps(std::string path, int current, int dest)
{
if (current > dest)
{
assert(false);
return;
}

if (current == dest)
{
printf("\n%s", path.c_str());
return;
}

CalculateSteps(path + "+1", current + 1, dest);

if (current + 2 <= dest)
{
CalculateSteps(path + "+2", current + 2, dest);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
// Test Cases:
// 0, 2 - +1+1, +2
// 0, 3 - +1+2, +1+1+1, +2,+1
printf("\n0-2");
CalculateSteps("", 0, 2);
printf("\n0-3");
CalculateSteps("", 0, 3);
return 0;
}

// StepsCalculator1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <cassert>

void CalculateSteps(std::string path, int current, int dest)
{
	if (current > dest)
	{
		assert(false);
		return;
	}

	if (current == dest)
	{
		printf("\n%s", path.c_str());
		return;
	}

	CalculateSteps(path + "+1", current + 1, dest);
	
	if (current + 2 <= dest)
	{
		CalculateSteps(path + "+2", current + 2, dest);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	// Test Cases:
	// 0, 2 - +1+1, +2
	// 0, 3 - +1+2, +1+1+1, +2,+1
	printf("\n0-2");
	CalculateSteps("", 0, 2);
	printf("\n0-3");
	CalculateSteps("", 0, 3);
	return 0;
}

// StepsCalculator1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <cassert>

void CalculateSteps(std::string path, int current, int dest)
{
	if (current > dest)
	{
		assert(false);
		return;
	}

	if (current == dest)
	{
		printf("\n%s", path.c_str());
		return;
	}

	CalculateSteps(path + "+1", current + 1, dest);
	
	if (current + 2 <= dest)
	{
		CalculateSteps(path + "+2", current + 2, dest);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	// Test Cases:
	// 0, 2 - +1+1, +2
	// 0, 3 - +1+2, +1+1+1, +2,+1
	printf("\n0-2");
	CalculateSteps("", 0, 2);
	printf("\n0-3");
	CalculateSteps("", 0, 3);
	return 0;
}

import java.util.HashMap;
import java.util.HashSet;



public class Stairs {


	static HashMap<Integer, HashSet<String>> memoize_map = new HashMap<Integer, HashSet<String>>();
	

	static HashSet<String> findWaysToClimbNStairs(int n)
	{
		System.out.println("calling findWaysToClimbNStairs for n =" + n);
		
		HashSet<String> strings = new HashSet<String> ();
		if (n < 1) return strings;
			
		HashSet<String> hs1 = new HashSet<String>();
		hs1.add("1");
		
		HashSet<String> hs2 = new HashSet<String>();
		hs2.add("11");
		hs2.add("2");
		
		memoize_map.put(0, new HashSet<String>());
		memoize_map.put(1, hs1);
		memoize_map.put(2, hs2);
		
		
		if (n == 1) 
		{	 
			return memoize_map.get(1);
		}
		
		if (n == 2)
		{
			return memoize_map.get(2);
			
		} 
		
		
		HashSet<String> waysToClimb1Less = memoize_map.get(n-1);
		if (waysToClimb1Less == null)
		{
			waysToClimb1Less = findWaysToClimbNStairs(n-1);
			memoize_map.put(n-1, waysToClimb1Less);
			
		} else {
			
			System.out.println("1) ready reuse for " + (n-1));
		}
		
		HashSet<String> waysToClimb2Less = memoize_map.get(n-2);
		if (waysToClimb2Less == null)
		{
			waysToClimb2Less = findWaysToClimbNStairs(n-2);
			memoize_map.put(n-2, waysToClimb2Less);
			
		} else {
			
			System.out.println("2) ready reuse for " + (n-2));
		}
		
		
		for (String wayToClimb1Less : waysToClimb1Less)
			strings.add("1" + wayToClimb1Less);
		
		for (String wayToClimb2Less : waysToClimb2Less)
			strings.add("2" + wayToClimb2Less);
		
		return strings;
		
	}

	public static void test_stairs(int n, int expected_count)
	{
		System.out.println("test stairs for n = " + n);
		 
		 
		HashSet<String> strings = findWaysToClimbNStairs(n );
		System.out.println("num ways for climbing " + n + " = " + strings.size());
		for (String s : strings)
		{ 
			System.out.println(s);
			
		}
		
		System.out.println("=== end of test stairs for n = " + n + " num ways = " + strings.size() 
				+ " expected num ways " + expected_count);
		
		if (strings.size() == expected_count)
			System.out.println("Matches expected count " + expected_count);
		else
			System.out.println("ERROR: Does not match expected count " + expected_count);
		
		System.out.println("End of test... \n\n\n");
	}
	
	
	public static void main(String[] args) {
		
		test_stairs(3, 3); //output == expected output = 3
		
		test_stairs(4, 5); //output == expected output = 5
		
		test_stairs(5, 8); //output == expected output = 8
		
	}

}

package test;

import java.util.ArrayList;
import java.util.Stack;

public class SubSets {
	
	public static void main(String[] args) {
            SubSets subSets = new SubSets();
            subSets.steps(3,null);
   	}
	
	
	public void steps(int num, Stack<Integer> stack) {
            if(null == stack){
        	stack = new Stack<Integer>();
            }
            int sum = getSum(stack);
            if(sum > num){
        	return;
            }else if(sum == num){
        	printStack(stack);
            }
        
            for(int i=1; i <= num; i++){
        	stack.push(i);
        	printAllpossibleStepsImpl2(num, stack);
        	stack.pop();
            }
        }
	
	private int getSum(Stack<Integer> stack){
		int sum = 0;
		for(Integer value: stack){
			sum += value;
		}
		return sum;
	}
	
	private void printStack(Stack<Integer> stack){
		for(Integer value: stack){
			System.out.print(value+"  ");
		}
		System.out.println();
	}
}

Javascript solution! You can paste it in a javascript console:

function stairs(n,array) { 
   if(array===undefined) array=[]; 
   if(n>=1) { 
      stairs(n-1,["1"].concat(array)); 
   } 
   if(n>=2) { 
      stairs(n-2,["2"].concat(array)); 
   } 
   if(n==0) console.log(array.join("")); 
}
stairs(5);

Note, I use array concatenation instead of string concatenation because it's faster.

Memorize sub-paths so we don't calculate it again.

public Set<String> stairs(int n) {
    List<Set<String>> list = new ArrayList<>();
    list.add(new HashSet<String>(){{ put(""); }}); // 0
    list.add(new HashSet<String>(){{ put("1"); }}); // 1
    for (int i = 2; i <= n; i++) {
        Set<String> set = new HashSet<>();
        for (String sub : list.get(i - 1)) {
            set.add("1" + sub);
        }
        for (String sub : list.get(i - 2)) {
            set.add("2" + sub);
        }
        list.add(set);
    }
    return list.get(n);
}

Recursive python generator function to do this

def stairs(n):
    if n == 0:
        yield ''
    elif n == 1:
        yield '1'
    else:
        for s in stairs(n-1):
            yield '1' + s
        for s in stairs(n-2):
            yield '2' + s


print [x for x in stairs(3)]

This is C++ version of solution. I used DFS with backtracking.

#include<iostream>
#include<list>

using namespace std;

void permutate(int left, list<int> option, list<list<int> >&result)
{
  if (left == 0)
  {
    result.push_back(option);
    return;
  } else if ( left < 0)
  {
    return;
  }

  for (int i = 1; i <=2; i++)
  {
    left -= i;
    option.push_back(i);
    permutate(left, option, result);
    left +=i;
    option.pop_back();
  }
}

list<list<int> > list_stairs(int steps)
{
  list<list<int> >result;
  list<int>option;
  int left = 0;
  for (int i = 1; i <=2; i++)
  {
    left = steps -i;
    option.push_back(i);
    permutate(left, option, result);
    option.pop_back();
  }
  return result;
}

int main()
{
  int target = 3;
  list<list<int> > result =list_stairs(target);
  list<list<int> >::iterator iter;
  for (iter = result.begin(); iter != result.end(); iter++)
  {
  list<int>::iterator i;
    for(i =(*iter).begin(); i != (*iter).end(); i++)
      cout<< *i;
    cout<<endl;
  }
}

recursive dynamic programming

public static void findSteps(int N){calSteps(N,"");};
	public static void calSteps(int N, String stepsNow){
		if(N >2){
			calSteps(N-2,stepsNow+"2");
		}
		else if(N == 2){
			System.out.println(stepsNow+"2");
		}
		if(N>1){
			calSteps(N-1,stepsNow+"1");
		}
		else if(N == 1){
			System.out.println(stepsNow+"1");
		}
	}

#import <Foundation/Foundation.h>
#import <stdio.h>

NSArray* stairs(int);

int main (int argc, const char * argv[])
{
  @autoreleasepool {
      for (NSArray *step in stairs(10)) {
          NSLog(@"%@", step);
      }
  }
}

NSArray* stairs(int n) {
    if (n == 0) {
        return @[@[]];
    }
    if (n == 1) {
        return @[@[@1]];
    }
    
    NSMutableArray *returnSteps = [NSMutableArray new];


    for (NSArray *steps in stairs(n-1)) {
        NSMutableArray *current = [NSMutableArray new];

        [current addObject: @1];
        [current addObjectsFromArray: steps];
        [returnSteps addObject: current];
    }

    for (NSArray *steps in stairs(n-2)) {
        NSMutableArray *current = [NSMutableArray new];

        [current addObject: @2];
        [current addObjectsFromArray: steps];
        
        [returnSteps addObject: current];
    }

    return returnSteps;

}

In Ruby 2.0:

# recursion requirement, this returns an array of array, which is
# array of all the possible steps to take, for n step staircase, and
# 1 or 2 steps possible each time

def all_ways(n)
  # this is tricky because it is 1 way if n = 0, which is "doing nothing"
  # it is not 0 way, it is 1 way
  return [[]] if n == 0
  
  result = []
  
  1.upto(2) do |n_steps|
    if n >= n_steps
      all_ways(n - n_steps).each do |possible_way|
        result.push([n_steps] + possible_way)
      end
    end
  end
  
  return result
end

def stairs(n)
  puts all_ways(n).map(&:join)
end

stairs(3)

In C#

static void Main(string[] args)
        {
            int stairs = 6;
            printSteps(stairs, "");
            Console.ReadKey(); // Optional
        }

        public static void printSteps(int steps, string res)
        {
            if(steps > 0) {
                printSteps(steps - 1, res + " 1");
                printSteps(steps - 2, res + " 2");
            } else if(steps == 0) {
                Console.WriteLine(res);
            }            
        }

max = binaryToDecimal(1111...(repeated "steps" times)
min = binaryToDecimal(0000...repeated "steps" times)
solutions = []
for (i in range(min, max)):
	currentSolution = ""
	for each bit j in i:
		currentSolution += j+1
	solutions.append(currentSolution)

return solutions

Use a Dinamic Programming approach; we only need to store the last 2 lists

public static List<string> GeneratePaths(int n)
{
	if (n <= 0)
		return new List<string>();
	
	var list1 = new List<string>();
	list1.Add("");
	
	var list2 = new List<string>();
	list2.Add("1");
	
	if (n == 1)
		return list1;
	
	for (int i=2; i <= n; i++)
	{
		var list = new List<string>();
		foreach (var item in  list2)
			list.Add(item + "1");
		foreach (var item in list1)
			list.Add(item + "2");
		
		list1.Clear();
		list1 = list2;
		list2 = list;
		
	}
	
	return list2;
}

Python 2.7 code:
{
memoized = {}
def stairs(N):
res = []
if N==1:
return [[1]]
elif N==2:
return [[1,1],[2]]
else:
if N in memoized:
return memoized[N]
re1 = stairs(N-1)
re2 = stairs(N-2)
for way in re1:
res.append([1]+way)
for way in re2:
res.append([2]+way)
memoized[N] = res

return res