【Leetcode】39. Combination Sum

╰+攻爆jí腚メ 2022-03-09 05:08 192阅读 0赞

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70]: /images/20220309/bdae30d451c04642b48946662ab0024c.png