Combination Sum

题目

Given a set of candidate numbers (C) (without duplicates) 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.
• The solution set must not contain duplicate combinations.

For example, given candidate set[2, 3, 6, 7]and target7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

思路分析

这道题定位应该是DFS，感觉就是用标准的DFS来实现。但是问题来了，这道题中有个问题是每一个数字可以unlimited得使用。如果每一个数字只用一次，那么比较容易想到，就是找数组的subset中和是target的。如果数组中的每一个数字可以unlimited使用，什么意思呢，可以带来什么信息呢？我就是在这个问题上被坑了很久，下面就是具体的分析：

• 数组中每一个数字只用一次

在写DFS递归函数的时候，每一个结点（数字）的下一层就是除了这个数字之外的其他的数，首先要对原数组进行排序，排完序之后可以避免重复子数组的出现，此时每一个结点（数字）的下一层就是除了这个数字之外的其他的比它大的数

dfs(candidates, target-candidates[I],i+1, path+[candidates[i]], result)

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def dfs(candidates, target, startIndex, path, result):
            if target < 0: return
            if target == 0:
                return result.append(path)
            for i in range(startIndex, len(candidates)):
                dfs(candidates, target-candidates[i], i+1, path+[candidates[i]], result)
        result = []
        dfs(sorted(candidates), target, 0, [], result)
        return result

• 数组中的每一个数字可以重复利用

在写DFS递归函数的时候，每一个结点（数字）的下一层是包含这个数的其他的数，首先要对原数组进行排序，排完序之后可以避免重复子数组的出现，此时每一个结点（数字）的下一层就是包含这个数字以及其他的比它大的数

dfs(candidates, target-candidates[i], i, path+[candidates[i]], result)

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def dfs(candidates, target, startIndex, path, result):
            if target < 0: return
            if target == 0:
                return result.append(path)
            for i in range(startIndex, len(candidates)):
                if target < candidates[i]: return
                dfs(candidates, target-candidates[i], i, path+[candidates[i]], result)
        result = []
        dfs(sorted(candidates), target, 0, [], result)
        return result