39. 组合总和

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

样例

Input：candidates = [2,3,6,7], target = 7,
Output：
[
  [7],
  [2,2,3]
]

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

题目解析

本题在 216. 组合总和 III(Medium) 的基础上，放宽了非重复数字的约束条件。其实更加简单了。

Python 代码示例

def backtracking(candidates, target, cur, ans, tmp):
    if sum(tmp) == target:
        ans.append(tmp[:])
        return 
    elif sum(tmp) > target:
        return 
    
    for i in range(cur, len(candidates)): # 从 cur 开始，可以避免走回头路
        tmp.append(candidates[i])
        backtracking(candidates, target, i, ans, tmp) # cur 从 i 开始相当于 可以重复
        tmp.pop()

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        backtracking(candidates, target, 0, ans, [])
        return ans