class Solution {
    public int climbStairs(int n) {
        int[] cache = new int[n + 1];
        cache[0] = 1;
        cache[1] = 1;

        helper(n, cache);
        return cache[n];
    }

    private int helper(int n, int[] cache) {
        if (cache[n] != 0) {
            return cache[n];
        }

        cache[n] = helper(n - 1, cache) + helper(n - 2, cache);
        return cache[n];

    }
}

class Solution {
    List<List<Integer>> ans; // переменная класса

    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        helper(0, new ArrayList<>(), n, k);
        return ans;
    }

    private void helper(int prev, List<Integer> comb, int n, int k) {
        if (comb.size() == k) {
            ans.add(new ArrayList<>(comb));
            return;
        }

        for (int i = prev + 1; i <= n; i++) {
            comb.add(i);
            helper(i, comb, n, k);
            comb.remove(comb.size() - 1);
        }
    }
}