生成n个数的所有长度为k的组合

Posted by daquexian on November 23, 2016

LeetCode第77题,这里是链接

给定两个正整数n, k,生成所有1~n的数的长度为k的组合,如k = 4, n = 2,结果是

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

一开始我的愚蠢方法是递归,结果果断超时,在讨论区看到一种绝妙的方法-w-,我改成了Python版:

class Solution(object):
    res = []
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """

        i = 0
        s = [0] * k
        res = []
        while True:
            s[i] += 1
            if s[i] > n:
                i -= 1
                if i >= 0:
                    continue
                break
            if i == k - 1:
                res.append(s[:])    
            else:
                i += 1
                s[i] = s[i - 1]
        
        return res