Implement Backtracking SearchStep 3 of 5

Combinations

12345

Step 3 - combinations

Implement combinations(n, k), returning all k-combinations of 1..n in lexicographic order.

Backtrack from start = 1, choosing ascending values and recursing with i + 1 so each chosen value is strictly larger than the previous. Append a copy when the path length reaches k.

For n = 4, k = 2 the output is [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]].

Hints
Starter code
def subsets(nums):
    res = []
    path = []
    def bt(start):
        res.append(list(path))
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res


def permutations(nums):
    res = []
    used = [False] * len(nums)
    path = []
    def bt():
        if len(path) == len(nums):
            res.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False
    bt()
    return res


def combinations(n, k):
    """Return all k-combinations of 1..n in lexicographic order.

    Choose ascending values; recurse with i + 1 so each value is larger
    than the previous.
    """
    # TODO: backtrack from start=1; append a copy when path length == k.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step