[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）：

 1 class Solution(object):
 2     def combine(self, n, k):
 3         """
 4         :type n: int
 5         :type k: int
 6         :rtype: List[List[int]]
 7         """
 8         def solve(index,n,k):
 9             ans = []
10             if k == n - index + 1:
11                 t = []
12                 for i in range(k):
13                     t.append(index)
14                     index += 1
15                 ans.append(t)
16                 return ans
17             if k == 1:
18                 while index <= n:
19                     ans.append([index])
20                     index += 1
21                 return ans
22             tmp1,tmp2 = solve(index + 1,n,k),solve(index + 1,n,k-1)
23             for i in tmp1:
24                 ans.append(i)
25             for i in tmp2:
26                 i = [index] + i
27                 ans.append(i)
28             return ans
29         return solve(1,n,k)

View Code

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