Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

  class Solution(object):
      def combinationSum(self, candidates, target):
          """
          :type candidates: List[int]
          :type target: int
          :rtype: List[List[int]]
          """
          res = []
          self.backtracking(res, candidates, target, [])
          return res

      def backtracking(self, res, candidates, target, sublist):
          #print target, sublist

          sum_sublist = sum(sublist)
          if sum_sublist == target:
              res.append(sublist)
              return
          delta = target - sum_sublist
          if delta < 0:
              return

          for item in candidates:
              if item > delta:
                  continue
              if sublist and item < sublist[-1]:
                  continue
              self.backtracking(res, candidates, target, sublist+[item])

不能重复选择的情况下 增加canidates为空的限制

  class Solution(object):
      def combinationSum2(self, candidates, target):
          """
          :type candidates: List[int]
          :type target: int
          :rtype: List[List[int]]
          """
          res = []
          # 增加一个处理过的index列表
          processed = []
          for index, item in enumerate(candidates):
              print index, item
              self.backtracking(res, candidates, target, [item], [index])
          return res

      def backtracking(self, res, candidates, target, sublist, processed):
          #print target, sublist

          sum_sublist = sum(sublist)
          if sum_sublist == target and sublist not in res:
              res.append(sublist)
              return
          delta = target - sum_sublist
          if delta < 0:
              return

          if candidates==[]:
              return

          for index, item in enumerate(candidates):
              if index in processed:
                  continue
              if item > delta:
                  continue

              if sublist and item < sublist[-1]:
                  continue
              self.backtracking(res, candidates, target, sublist+[item], processed+[index])
              # 关键点是backtracking后面processed这个参数的传输