title: All combinations of 1 + 2 that adds to n
body: <p>I am trying to solve this question as the preparation for a programming interview: </p>
  
  <blockquote>
    <p>A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.</p>
    
    <p>Write a function that calculates the number of different combinations a frog can use to cover a given distance.</p>
    
    <p>For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.</p>
  </blockquote>
  
  <p>I think there is a quite simple solution to this, but I just can't seem to find it. I would like to use recursion, but I can't see how. Here is what I have so far:</p>
  
  <pre><code>public class Frog {
  
      static int combinations = 0;
      static int step = 1;
      static int jump = 2;
      static int[] arr = {step, jump};
  
      public static int numberOfWays(int n) {
          for (int i = 0; i &lt; arr.length; i++) {
              int sum = 0;
              sum += arr[i];
              System.out.println("SUM outer loop: " + sum + " : " + arr[i]);
              while (sum != 3) {
                  for (int j = 0; j &lt; arr.length; j++) {
                      if (sum + arr[j] &lt;= 3) {
                          sum += arr[j];
                          System.out.println("SUM inner loop: " + sum + " : " + arr[j]);
                          if (sum == 3) {
                              combinations++;
                              System.out.println("Combinations " + combinations);
                          }
                      }
                  }
              }
          }
          return combinations;
      }
  
      public static void main(String[] args) {
          System.out.println(numberOfWays(3));
      }
  }
  </code></pre>
  
  <p>It doesn't find all combinations, and I think the code is quite bad. Anyone have a good solution to this question? </p>