Combinations - Implementation

Here is the full solution:

function combine(n, k)
    result := []
    backtrack(1, [], n, k, result)
    return result

function backtrack(start, current, n, k, result)
    if length of current = k then
        add copy of current to result
        return
    for i from start to n
        add i to current
        backtrack(i + 1, current, n, k, result)
        remove last element from current

Time: $O(C(n, k) \times k)$ to generate and copy all combinations. Space: $O(k)$ for recursion depth and current combination.