leetcode: 77. Combinations

Problem

# 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],
# ]

AC

DFS:

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]]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券