数字组合 II

yingl · yingl · commit 0307940b8b9c · 2016-08-29T18:03:41.000+08:00
diff --git a/combination_sum_ii.py b/combination_sum_ii.py
@@ -0,0 +1,32 @@
+# -*- coding: utf-8 -*-
+
+class Solution:    
+    """
+    @param candidates: Given the candidate numbers
+    @param target: Given the target number
+    @return: All the combinations that sum to target
+    """
+    def combinationSum2(self, candidates, target): 
+        # write your code here
+        self.ret = []
+        self.target = target
+        candidates.sort()
+        self._combinationSum2(candidates, [], 0, 0)
+        return self.ret
+        
+    def _combinationSum2(self, candidates, comb, i, _sum):
+        if _sum == self.target:
+            self.ret.append(comb[:])
+        elif _sum > self.target:
+            return
+        else:
+            if i <= len(candidates):
+                prev = None
+                j = i
+                while j < len(candidates):
+                    if candidates[j] != prev:
+                        prev = candidates[j]
+                        comb.append(candidates[j])
+                        self._combinationSum2(candidates, comb, j + 1, _sum + prev)
+                        comb.pop()
+                    j += 1
