leetcode: 77. Combinations

# Given two integers n and k, 
# return all possible combinations of k numbers out of 1 ... n.
#
# For example,
# If n = 4 and k = 2, a solution is:
#
# [
#   [2,4],
#   [3,4],
#   [2,3],
#   [1,2],
#   [1,3],
#   [1,4],
# ]

class Solution():
    def combine(self, n, k):
        res = []
        self.dfs(res, n, k, 1, [])
        return res
    def dfs(self, res, n, k, start, path):
        if not k:
            res.append(path)
            return
        for i in range(start, n+1):
            self.dfs(res, n, k-1, i+1, path+[i])


if __name__ == "__main__":
    assert Solution().combine(4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]