Find all the ways you can go up an n step staircase if you can take k steps at a time such that k <= n
<p>This is a problem I'm trying to solve on my own to be a bit better at recursion(not homework). I believe I found a solution, but I'm not sure about the time complexity (I'm aware that DP would give me better results).</p>

<blockquote>
  <p>Find all the ways you can go up an n step staircase if you can take k steps at a time such that k &lt;= n</p>
</blockquote>

<p>For example, if my step sizes are [1,2,3] and the size of the stair case is 10, I could take 10 steps of size 1 [1,1,1,1,1,1,1,1,1,1]=10 or I could take 3 steps of size 3 and 1 step of size 1 [3,3,3,1]=10</p>

<p>Here is my solution:</p>

<pre><code>static List&lt;List&lt;Integer&gt;&gt; problem1Ans = new ArrayList&lt;List&lt;Integer&gt;&gt;();
public static void problem1(int numSteps){
    int [] steps = {1,2,3};
    problem1_rec(new ArrayList&lt;Integer&gt;(), numSteps, steps);
}
public static void problem1_rec(List&lt;Integer&gt; sequence, int numSteps, int [] steps){
    if(problem1_sum_seq(sequence) &gt; numSteps){
        return;
    }
    if(problem1_sum_seq(sequence) == numSteps){
        problem1Ans.add(new ArrayList&lt;Integer&gt;(sequence));
        return;
    }
    for(int stepSize : steps){
        sequence.add(stepSize);
        problem1_rec(sequence, numSteps, steps);
        sequence.remove(sequence.size()-1);
    }
}
public static int problem1_sum_seq(List&lt;Integer&gt; sequence){
    int sum = 0;
    for(int i : sequence){
        sum += i;
    }

    return sum;
}
public static void main(String [] args){
    problem1(10);
    System.out.println(problem1Ans.size());

}
</code></pre>

<p>My guess is that this runtime is k^n where k is the numbers of step sizes, and n is the number of steps (3 and 10 in this case).</p>

<p>I came to this answer because each step size has a loop that calls k number of step sizes. However, the depth of this is not the same for all step sizes. For instance, the sequence [1,1,1,1,1,1,1,1,1,1] has more recursive calls than [3,3,3,1] so this makes me doubt my answer.</p>

<p>What is the runtime? Is k^n correct?</p>