How to add recursively function

Question

I am confused how to write this in JAVA: There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

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.

Basically, I could do the first part and understand the logics with harder part with the set that the answer is: f(n) = f(n-1) + f(n-3) + f(n-5). Can anyone help me? This is mine approach:

public static void main(String[] args) {
 int n = 4;
 Set < Integer > list = new HashSet < Integer > ();
 list.add(1);
 list.add(3);
 list.add(5);
 int ways = reachNFloorSet(list, n, 0);
 //     int ways = reachNFloor(n);
 System.out.println(n + " Floor is reached in " + ways + " different way/s.");
}


public static int reachNFloor(int n) { // easy part
 if (n <= 1) {
  return 1;
 }
 return reachNFloor(n - 1) + reachNFloor(n - 2);
}

public static int reachNFloorSet(Set < Integer > numbers, int n, int sum) {
 if (n < 0) {
  return 0;
 } else if (n == 0) {
  return 1;
 }

 for (Integer x: numbers) {
  if (x <= n) {
   sum += reachNFloorSet(numbers, n - x, sum);
  }
 }
 return sum;
}

I think that the problem is with the for loop, but I cannot figure how to make it correct.

Answer 1

When n is negative or 0 in reachNFloorSet(), you're returning 0 or 1, but you should be returning sum or sum + 1. Otherwise you're throwing away all the accumulated info.

It would be better, I think, to rewrite your method so it doesn't have to worry about how many steps have already been taken:

public static int reachNFloorSet (Set<Integer> numbers, int n) {
    if (n == 0) {
        return 1;
    }

    int sum = 0;
    for(Integer x: numbers) {

        if (x <= n) {

            sum += reachNFloorSet(numbers, n-x);

        }
    }
    return sum;
}

You don't have to worry about n being negative, because you don't make recursive calls where that could happen. (Of course, you should guard against negative n in the original call as well.)