Count and display ways to climb staircase java

Question

I wrote some code to count and also print the number of ways to climb a given staircase with n steps.

It is only possible to climb 1 or 2 stairs at a time. I know this is a known interview question and I have some code I wrote to share with you.

The problem is i am missing a lot of sequences. Can you please review and help me understand what logic I am missing? Thanks for your help

My code:

/**
 * 
 */
package prep;

/**
 * @author rohandalvi
 *
 */
public class generateAllPermutations {

    /**
     * @param args
     */
    static int totalCounter = 0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int numberOfStairs = 10;
        int countSoFar = 0;
        String path = "";
        for(int i=1;i<3;i++){
            path = ""+i;
            displayAllPerms(numberOfStairs, i, path);
        }
        System.out.println("Total combinations found "+totalCounter);
    }

    public static void displayAllPerms(int n,int countSoFar,String s){
        if(countSoFar > n) return;
        else if(countSoFar < n){
            for(int i=1;i<3;i++){
                s+=" "+i;
                countSoFar+=i;
                displayAllPerms(n, countSoFar, s);
            }
        }else{
            System.out.println("Found combination "+s);
            totalCounter++;
            return;
        }
    }

}

Result:

Found combination 1 1 1 1 1 1 1 1 1 1
Found combination 1 1 1 1 1 1 1 1 2
Found combination 1 1 1 1 1 1 1 2 1
Found combination 1 1 1 1 1 1 2 1 1
Found combination 1 1 1 1 1 2 1 1 1
Found combination 1 1 1 1 1 2 1 2
Found combination 1 1 1 1 2 1 1 1 1
Found combination 1 1 1 1 2 1 1 2
Found combination 1 1 1 1 2 1 2 1
Found combination 1 1 1 2 1 1 1 1 1
Found combination 1 1 1 2 1 1 1 2
Found combination 1 1 1 2 1 1 2 1
Found combination 1 1 1 2 1 2 1 1
Found combination 1 1 2 1 1 1 1 1 1
Found combination 1 1 2 1 1 1 1 2
Found combination 1 1 2 1 1 1 2 1
Found combination 1 1 2 1 1 2 1 1
Found combination 1 1 2 1 2 1 1 1
Found combination 1 1 2 1 2 1 2
Found combination 2 1 1 1 1 1 1 1 1
Found combination 2 1 1 1 1 1 1 2
Found combination 2 1 1 1 1 1 2 1
Found combination 2 1 1 1 1 2 1 1
Found combination 2 1 1 1 2 1 1 1
Found combination 2 1 1 1 2 1 2
Found combination 2 1 1 2 1 1 1 1
Found combination 2 1 1 2 1 1 2
Found combination 2 1 1 2 1 2 1
Found combination 2 1 2 1 1 1 1 1
Found combination 2 1 2 1 1 1 2
Found combination 2 1 2 1 1 2 1
Found combination 2 1 2 1 2 1 1

Basically, I am missing combinations like:

2 2 2 2 2

And a lot more combinations, basically all starting with 2 2

Answer 1

Let me start by stating a recursive approach for this problem, that I suspect you have taken. Then, I will move on to the code.

Ways to climb 3 steps = [ways to climb 2 steps] + [ways to climb 1 step].

Generalizing, ways to climb n steps = [ways to climb n-1 steps] + [ways to climb n-2 steps].

If you haven't noticed, this is the Fibonacci pattern (alternative solution is to simply return the n+1^th Fibonacci number; try it out!).

public int getWays(int n) {
    if(n <= 1) return n;

    int result = 0;
    for (int i = 1; (i <= 2 && i <= n); i++)
        result += getWays(n-i);
    return result;
}

// Usage:
int steps = 4;
getWays(steps + 1);    // 5 ways

Now, if you want to look at the combinations taken. I am taking a slightly different approach that I think is more intuitive.

public static void waysToReachN(int currentValue, int n, List<Integer> pathSoFar) {
    if(currentValue == n) {
        System.out.println(pathSoFar);
        return;
    } else if(currentValue > n) {
        return;
    }
    for(int i = 1 ; i <= 2 ; i++) {
        // add step
        pathSoFar.add(i);

        // recurse
        waysToReachN(currentValue + i, n, pathSoFar);

        // remove step
        pathSoFar.remove(pathSoFar.size()-1);
    }
}

// Usage:
int currentValue = 0, n = 4;
waysToReachN(currentValue, n, new ArrayList<Integer());

So, we had found that there were 5 ways to climb 4 stairs. The ways are,

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]

Please let me know if something is not clear.