39.combination_sum.md

39. Combination Sum

中等

https://leetcode.cn/problems/combination-sum/

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

相关企业

• 亚马逊 Amazon|21
• Facebook|14
• 字节跳动|7
• 微软 Microsoft|6
• 苹果 Apple|4
• 彭博 Bloomberg|3
• 领英 LinkedIn|3
• 高盛集团 Goldman Sachs|2

相关标签

• Array
• Backtracking

相似题目

• Letter Combinations of a Phone Number 中等
• Combination Sum II 中等
• Combinations 中等
• Combination Sum III 中等
• Factor Combinations 中等
• Combination Sum IV 中等

sol1 dfs

时间复杂度：O(n^{target/min})

, （拷贝过程视作O(1),n为集合中数字个数，min为集合中最小的数字 每个位置可以取集合中的任意数字，最多有target/min个数字。

空间复杂度：O(n^{target/min})

, n为集合中数字个数，min为集合中最小的数字 对于用来保存答案的列表，最多有target/min 种组合

hard point

与 Subsets 比较

• Combination Sum 限制了组合中的数之和

  • 加入一个新的参数来限制

• Subsets 无重复元素，Combination Sum 有重复元素

  • 需要先去重

• Subsets 一个数只能选一次，Combination Sum 一个数可以选很多次 unlimited use-time for each node

  • 搜索时从 index 开始而不是从 index + 1. change i+1 to i in recursion

python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []

        candidatesSorted = sorted(candidates)
        results = []
        self.dfs(candidatesSorted, 0, [], results, target)
        return results

    def dfs(self, candidatesSorted, currIndex, currSubset, results, remainTarget):
        if remainTarget == 0:
            results.append(list(currSubset))
        
        for i in range(currIndex, len(candidatesSorted)):
            if remainTarget < candidatesSorted[i]:
                break
            currSubset.append(candidatesSorted[i])
            self.dfs(candidatesSorted, i, currSubset, results, remainTarget - candidatesSorted[i])
            currSubset.remove(candidatesSorted[i])

python 语法 之 list的“+“

def dfs(self, candidatesSorted, currIndex, currSubset, results, remainTarget):
        if remainTarget == 0:
            results.append(currSubset) # 如果用+则这里不需hard copy
            return
        if remainTarget < 0:
            return
        
        for i in range(currIndex, len(candidatesSorted)):
            if remainTarget < candidatesSorted[i]:
                return
            self.dfs(candidatesSorted, i, 
                    currSubset + [candidatesSorted[i]], # 可以用+但是不推荐，因为+实际是复制成一个新的list，时间为O(len(list))
                    results, remainTarget - candidatesSorted[i])