数字组合

yingl · yingl · commit 80b945e13ae3 · 2016-08-29T17:57:19.000+08:00
diff --git a/combination_sum.py b/combination_sum.py
@@ -0,0 +1,33 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param candidates, a list of integers
+    # @param target, integer
+    # @return a list of lists of integers
+    def combinationSum(self, candidates, target):
+        # write your code here
+        self.ret = []
+        self.target = target
+        candidates.sort()
+        self._combinationSum(candidates, [], 0, 0)
+        return self.ret
+        
+    def _combinationSum(self, candidates, comb, i, _sum):
+        if _sum == self.target:
+            self.ret.append(comb[:])
+        elif _sum > self.target:
+            return
+        else:
+            if i <= len(candidates):
+                comb.append(candidates[i])
+                self._combinationSum(candidates, comb, i, _sum + candidates[i])
+                comb.pop()
+                prev = candidates[i]
+                j = i
+                while j < len(candidates):
+                    if candidates[j] != prev:
+                        prev = candidates[j]
+                        comb.append(candidates[j])
+                        self._combinationSum(candidates, comb, j, _sum + prev)
+                        comb.pop()
+                    j += 1
