[LeetCode]题解（python）：077-Combinations

题目来源：

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

题意分析：

　　给定一个n和k，输出1到n的所有k个数的组合。比如n = 4，k=2

[

  [2,4],

  [3,4],

  [2,3],

  [1,2],

  [1,3],

  [1,4],

]

题目思路：

　　这道题目用递归的思想来做。比如我们把n当成一个数字[1,2,...,n]，如果组合包括1那么[2,..,n]和k-1的所有答案添加一个1；如果组合不包括1，那么答案是[2,...,n]和k的组合。然后将两个组合结合起来就可以了。初始化，如果n == k，那么组合就是直接所有的数，如果k == 1，那么组合是每一个数。

代码（Python）：

 class Solution(object):

     def combine(self, n, k):

         """

         :type n: int

         :type k: int

         :rtype: List[List[int]]

         """

         def solve(index,n,k):

             ans = []

             if k == n - index + 1:

                 t = []

                 for i in range(k):

                     t.append(index)

                     index += 1

                 ans.append(t)

                 return ans

             if k == 1:

                 while index <= n:

                     ans.append([index])

                     index += 1

                 return ans

             tmp1,tmp2 = solve(index + 1,n,k),solve(index + 1,n,k-1)

             for i in tmp1:

                 ans.append(i)

             for i in tmp2:

                 i = [index] + i

                 ans.append(i)

             return ans

         return solve(1,n,k)

转载请注明出处：http://www.cnblogs.com/chruny/p/5088520.html

巴特西

[LeetCode]题解（python）：077-Combinations

最新文章

热门文章