#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/combinations/combinations-implementation-3

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/combinations/combinations-implementation-3

Repovive

Combinations - Implementation - Combinations | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Combinations - Implementation

The pseudocode

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.