переход назад по n лестницам не более чем к k ступеням за один прыжок

Одна огромная проблема заключается в приведенном ниже коде: вы вычитаете количество шагов для каждой возможности в пределах диапазона шагов.

n=n-i
res=CSR(n,i,res)

Когда вы закончите изучать, что можно сделать с 1-шаговым прыжком, вам нужно вернуться назад и попробовать с той же начальной точки (исходное значение этого экземпляра n) с 2-х ступенчатым прыжком. Измените код на:

res = CSR(n-i, i, res)

Это сохраняет значение n неизменным при прохождении цикла.

Кроме того, вы не можете ограничивать будущие прыжки максимумом того, что вы только что сделали. Измените и этот второй параметр:

res = CSR(n-i, k, res)

Это должно заставить вас двигаться. Также попробуйте этот замечательный блог debug, чтобы получить помощь. По крайней мере, вставьте один или два оператора трассировки, например

print n, k, res

на вершине вашей рутины.

CAVEAT

Это не все твои беды. Самая большая оставшаяся проблема заключается в том, что CSR возвращает только одно решение: каждый сделанный вами шаг добавляется в тот же список. Вам нужен способ собрать готовые решения в отдельные списки; append в climbingStaircase выполняется только один раз после полного завершения CSR.

Вы должны узнать законченное решение на n==0.

ПОМОЩЬ ПО ОТЛАДКЕ

Вот версия вашей программы с исправленными параметрами рекурсии и вставленными трассировками отладки.

indent = ""

def climbingStaircase(n, k):
    final_res = []
    final_res.append(CSR(n, k, []))
    return final_res

def CSR(n, k, res):
    global indent
    indent += "  "
    print indent, n, k, res
    if n == 0:
        print "SOLUTION", res
    else:
        for i in range(1, k+1):
            if n-i >= 0:
                CSR(n-i, k, res + [i])
    indent = indent[:-2]

print climbingStaircase(4, 2)

Обратите внимание на использование «отступа», чтобы помочь визуализировать рекурсию и возврат. Важным моментом здесь является то, что вместо глобального обновления res я оставил его как локальную переменную. Я также удалил возвращаемое значение, просто сбросив его, чтобы вывести решения в том виде, в каком они были найдены. Вы можете увидеть, как это работает:

   4 2 []
     3 2 [1]
       2 2 [1, 1]
         1 2 [1, 1, 1]
           0 2 [1, 1, 1, 1]
SOLUTION [1, 1, 1, 1]
         0 2 [1, 1, 2]
SOLUTION [1, 1, 2]
       1 2 [1, 2]
         0 2 [1, 2, 1]
SOLUTION [1, 2, 1]
     2 2 [2]
       1 2 [2, 1]
         0 2 [2, 1, 1]
SOLUTION [2, 1, 1]
       0 2 [2, 2]
SOLUTION [2, 2]
[None]

Я надеюсь, что с этим материалом вы сможете проследить свою логику и выяснить, как зафиксировать последовательность решений на выбранном вами уровне.

Успешно реализован ответ Prune.

def climbingStaircase(n, k):
    res=[]
    CSR(n,k,[],res)
    return res

def CSR(n,k,str_, res):
    if n == 0:
        res.append(str_)
    else:
        for i in range(1,k+1):
            if n-i>=0:
                CSR(n-i,k,str_+[i],res)

Быстрая версия этого решения на Java:

int[][] climbingStaircase(int n, int k) {
    List<ArrayList<Integer>> list = new ArrayList<>();
    climb(n, k, new ArrayList<Integer>(), list);

    // convert to int[][]
    int[][] result = new int[list.size()][];
    for (int i=0; i<list.size(); i++) {
        List<Integer> l = list.get(i); 
        int [] arr = new int[l.size()];
        for (int j=0; j<l.size(); j++)
            arr[j] = l.get(j);
        result[i] = arr;
    }
    return result;
}
void climb(int n, int k, ArrayList<Integer> prev, List<ArrayList<Integer>> list) {
    if (n==0) { // no more stairs, done climbing
        list.add(prev);
    } else {
        for (int i=1; i<=k; i++) { // climb remaining stairs in intervals from 1 to k steps
            if (i <= n) { // no need to test intervals larger than remaining # of stairs
                ArrayList<Integer> branch = new ArrayList<>(prev);
                branch.add(i);
                climb(n-i, k, branch, list);
            }
        }
    }
}