Combinations

def combine(n, k):
    res, path = [], []
    def back(start):
        if len(path) == k:
            res.append(path[:])
            return
        last = n - (k - len(path)) + 1
        for i in range(start, last + 1):
            path.append(i)
            back(i + 1)
            path.pop()
    back(1)
    return res

Combinations. Given n and k, return every way to choose k numbers from one to n. Order doesn't matter: one, two and two, one are the same team.

With n equals four and k equals two, there are six: one two, one three, one four, two three, two four, and three four. For n one and k one, the only answer is one.

The direct way: build all two to the n subsets, and keep those with exactly k. For n equals four, that's sixteen subsets built and only six kept. The rest is wasted.

The key idea: backtrack with a start index. Pick the next number from start up to n, then recurse with start just past it. Numbers only go up: no duplicates, no reorderings. When the path holds k numbers, record it. It's Subsets, stopped at size k. And prune: stop early when too few numbers are left.

In code, if the path has k numbers, save a copy. Otherwise, loop from start to n, minus the numbers still needed, plus one. Pick a number, recurse from the next one, then unpick it.

Now four and two. Pick one, then two: full, record one two. Unpick two, try three, then four. Unpick one, pick two: two three, two four. Then three four. Four is never picked first: nothing would be left after it. Six combinations.

There are n choose k answers, and copying each costs k: order k times n choose k time. The path goes k deep: order k space.

Pick, recurse, unpick. That's Combinations.