Backtracking N stairs question getting 0 cases Java

Question

N Stairs question is to compute the number of distinct ways to reach the top. Each time you can either climb 1 or 2 steps. For example, if the input is 3, the desired output is 3 (1+1+1,1+2,2+1).

I am learning backtracking in Java, so I want to implement it in this question, although DP would work better in such a case. I view it as a practice if I understand backtracking well, but apparently not. I got stuck because my algorithm gives me a 0 output for every case. Below is my code:

    public int climbStairs(int n) {
        int cnt=0,k=0;
        climb(cnt,k,n);
        return cnt;
    }
    public void climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
            return; 
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
    }

Could you help me figure out what's wrong with my code? I tried debugging it, and I noticed every time it returns, cnt will automatically change to 0, but I just can't figure out why.

Thank you so much in advance!

Edited version:

public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }
    public static int climbStairs(int n) {
        int cnt=0,k=0;
        return climb(cnt, k, n);
    }
    public static int climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
        return cnt;
    }
}

Answer 1

Java is pass-by-value. That means your that your cnt variable in your climbStairs method is not shared; it is unique to you. When you invoke climb, you pass the value it holds (0 every time here), and climb has its own variable (also called cnt). It modifies its own cnt value which is tossed in the garbage when that method ends (all parameters and all local variables are always tossed in the garbage when a method ends).

You want to return cnt:

// In climbStairs:
return climb(cnt, k, n);

// In climb, at the end:
return cnt;

Answer 2

We are given that there are N steps. Let n equal the number of two-steps taken (0 <= n <= N/2). If n two-steps are taken N-2*n one-steps are taken.

Let f(n) equal the number of combinations of one-steps and two-steps when there are n two-steps. This is merely a coefficient in a multinomial distribution having two distinct items:

m = N-2*n
f(n) = (n+m)!/(n!*m!)

To obtain the desired total number of combinations we simply sum f(n) over n = 0..N/2.

---

For N = 3 (the example given in the question), the number of combinations is computed as follows.

n = 0
m = N-2*n = 3
f(n) = (n+m)!/(n!*m!) = 3!/(0!*3!) = 1    # 111

n = 1
m = N-2*n = 1
f(n) = (n+m)!/(n!*m!) = 2!/(1!*1!) = 2    # 12 and 21

f(0) + f(1) = 3

---

For N = 5, the number of combinations is computed as follows.

n = 0
m = N-2*n = 5
f(n) = (n+m)!/(n!*m!) = 5!/(0!*5!) = 1    # 11111

n = 1
m = N-2*n = 3
f(n) = (n+m)!/(n!*m!) = 4!/(1!*3!) = 4    # 2111 1211 1121 1112

n = 2
m = N-2*n = 1
f(n) = (n+m)!/(n!*m!) = 3!/(2!*1!) = 3    # 212 221 122

f(0) + f(1) + f(2) = 8