Combination Sum

题目描述

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

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

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target `7,

A solution set is:

[7] 
[2, 2, 3]

解题方法

• 有顺序，non-descending,所以应该用subset那种方法
• 可以重复使用，所以DFS时应该继续包括当前的number
• 都是Positive,所以当当前List的和已经大于target,就可以结束了
• 重复依然要去除

Solution

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        results = []
        if not candidates:
            return [[]]
        candidates.sort()
        self.combHelper(results, candidates, target, 0, [])
        return results

    def combHelper(self, results, candidates, target, index, curList):
        if sum(curList) == target:
            tmpList = list(curList)
            results.append(tmpList)
        elif sum(curList) > target:
            return

        for i in range(index, len(candidates)):
            if i != index and candidates[i] == candidates[i-1]:
                continue
            curList.append(candidates[i])
            self.combHelper(results, candidates, target, i, curList)
            curList.pop()

Reference