程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Combinations

LeetCode Combinations

編輯:C++入門知識

LeetCode Combinations


LeetCode解題之Combinations


原題

求在1到n個數中挑選k個數的所有的組合類型。

注意點:

每個數字只能夠用一遍 組合的排列沒有順序要求

例子:

輸入: n = 4, k = 2

輸出: [[1, 4], [2, 4], [3, 4], [1, 3], [2, 3], [1, 2]]

解題思路

采用遞歸的方式,在n個數中選k個,如果n大於k,那麼可以分類討論,如果選了n,那麼就是在1到(n-1)中選(k-1)個,否則就是在1到(n-1)中選k個。遞歸終止的條件是k為1,這時候1到n都符合要求。

AC源碼

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if k == 1:
            return [[i + 1] for i in range(n)]
        result = []
        if n > k:
            result = [r + [n] for r in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)
        else:
            result = [r + [n] for r in self.combine(n - 1, k - 1)]
        return result


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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved