【Leetcode】39. Combination Sum-蒲公英云

【Leetcode】39. Combination Sum

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.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题目大意：

从给出的数组中，找出和为target的组合。给出的列表中不存在重复数据，但是答案中可以重复使用。注意：给出的列表不是排序之后的List。

解题思路：

我们可以看出每个数最多的使用次数是int(target/candidates[i])。并且超过target的数据不会出现在答案中，所以我们可以先求出每个数在答案当中出现的最多个数，同时求出我们寻找可能组合的最大范围（减少时间开销）。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70

eg 2 3 6就是我们需要遍历的范围

在遍历的过程中，维护好数字对应的数量List，DFS就可以。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        len_c = len(candidates)
        # print(len_c)
        num = [0] * len_c
        len_max = len_c
        for i in range(len_c):
            num[i] += int(target / candidates[i])
            if num[i] == 0 and i < len_max:
                len_max = i
        # print(len_max, num)
        ans = []
        tmp = []
        began = 0
        return DFS(ans, tmp, 0, target, len_max ,num, candidates,began)
def DFS(ans, tmp, cor, target, len_max, num, candidates, began):
    if cor > target:
        return ans
    if cor == target:
        new_ans = []
        for i in range(len(tmp)):
            new_ans.append(tmp[i])
        ans.append(new_ans)
        return ans
    for i in range(began, len_max):
        if num[i] != 0 and cor + candidates[i] <= target:
            tmp.append(candidates[i])
            num[i] -= 1
            cor += candidates[i]
            ans = DFS(ans, tmp, cor, target, len_max, num, candidates, i)
            tmp.pop()
            num[i] += 1
            cor -= candidates[i]
    return ans