Problem statement

https://leetcode.com/problems/combinations/

Solution

Classical backtracking problem, good for practice. The idea is to use helper(current), where current is built combination so far. Each time we check if we already built all combination and if yes, add it to self.out, if not: try to add new elements.

Complexity

It is O(k*2^n), more accurate is (k*C_n^k) for time and space.

Code

class Solution:
    def combine(self, n, k):
        def helper(current):
            if len(current) == k+1:
                self.out.append(current[1:])
            else:
                for i in range(current[-1]+1, n+1):
                    helper(current + [i])
        
        self.out = []
        helper([0])
        return self.out