Climbing Staircase

You need to climb a staircase that has n steps, and you decide to get some extra exercise by jumping up the steps. You can cover at most k steps in a single jump. Return all the possible sequences of jumps that you could take to climb the staircase, sorted.

Example

For n = 4 and k = 2, the output should be

solution(n, k) =
[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

There are 4 steps in the staircase, and you can jump up 2 or fewer steps at a time. There are 5 potential sequences in which you jump up the stairs either 2 or 1 at a time.

Input/Output

[execution time limit] 3 seconds (java)
[memory limit] 1 GB
[input] integer n

Guaranteed constraints:

0 ≤ n ≤ 10.
[input] integer k

Guaranteed constraints:

0 ≤ k ≤ n.
[output] array.array.integer

An array containing all of the possible sequences in which you could climb n steps by taking them k or fewer at a time.

풀이

int[][] solution(int n, int k) {
    // 배열들을 담을 가변형 자료구조
    LinkedList<int []> list = new LinkedList <> ();
    // 파라미터 목적의 가변형 자료구조
    LinkedList <Integer> current = new LinkedList <>();
    // 백트래킹 시작
    findSequences(n, k, 0, current, list);
    
    int [][] result = new int [list.size()][];
    int idx = 0;
    
    for (int [] arr : list) {
        result[idx ++] = arr;
    }    
    
    return result;
}

// n 목표 계단 높이
// k 최대 점프 높이
// currentStep 현재 높이
void findSequences(int n, int k, int currentStep, LinkedList<Integer> current, LinkedList<int []> result) {
    // 목표에 도착
    if (currentStep == n) {
        int [] buff = new int [current.size()];
        
        for (int i = 0; i < buff.length; i ++) {
            buff[i] = current.get(i);
        }
        // 가변형 자료구조에 추가
        result.add(buff);
        // 종료
        return;
    }
    // 점프 높이는 1 ~ k
    // 점프가 최대 점프 높이보다 작거나 같고
    // 현재 높이와 점프 높이가 목표 높이와 작거나 같을 때 까지 순회
    for (int jump = 1; jump <= k && currentStep + jump <= n; jump++) {
        current.add(jump);
        findSequences(n, k, currentStep + jump, current, result);
        current.remove(current.size() - 1);
    }
}