组合

yingl · yingl · commit 2176a5674935 · 2016-08-12T11:08:55.000+08:00
diff --git a/combinations.py b/combinations.py
@@ -0,0 +1,34 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """    
+    @param n: Given the range of numbers
+    @param k: Given the numbers of combinations
+    @return: All the combinations of k numbers out of 1..n   
+    """
+    def combine(self, n, k):      
+        # write your code here
+        # TODO: 添加注释
+        list = [x + 1 for x in xrange(n)]
+        return self.dfs(list, 0, k)
+        
+    def dfs(self, list, pos, k):
+        n = len(list) - pos
+        if (not list) or (n < k):
+            return None
+        ret = []
+        if k == 0:
+            return [[]]
+        elif k == 1:
+            for i in xrange(pos, len(list), 1):
+                ret.append([list[i]])
+            return ret
+        else:
+            for i in xrange(pos, len(list), 1):
+                combs = self.dfs(list, i + 1, k - 1)
+                if combs:
+                    for comb in combs:
+                        new_comb = [list[i]]
+                        new_comb.extend(comb)
+                        ret.append(new_comb)
+            return ret
