# \[39]\[中等]\[回溯] 组合总和

## 题目描述

[39. 组合总和](https://leetcode-cn.com/problems/combination-sum/)

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

candidates 中的数字可以无限制重复被选取。

说明：

* 所有数字（包括 target）都是正整数。
* 解集不能包含重复的组合。

示例 1：

```
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]
```

示例 2：

```
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
```

提示：

* 1 <= candidates.length <= 30
* 1 <= candidates\[i] <= 200
* candidate 中的每个元素都是独一无二的。
* 1 <= target <= 500

## 解题思路

找出所有组合, 因此需要使用回溯. 而本题的关键是在于不能包含重复组合, 因此在回溯的过程中需要合理的剪枝, 避免重复组合的出现.

对于第一个例子, `[2, 2, 3]`和`[3, 2, 2]`属于同一个结果, 因此我们可以限制下一层搜索的起点. `[2, 2, 3]`是先搜完2再搜3得到的结果, `[3, 2, 2]`则相反. 由于原数组中的元素不重复, 因此我们可以规定, 每一层搜索从指定位置开始, 包括指定位置, 只能向后不能向前搜索. 例如对于数组`[2,3,6,7]`, 当我们在某层第一个搜索的数字是3时, 下一层就只能从3开始(数字可以被无限制重复选取), 但不能再搜索2了.

这样就能避免重复结果的出现. 对应的代码为:

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []

        def dfs(path, tar, start):
            if tar == 0:
                results.append(path[:])
                return
            if tar < 0:
                return

            for i, num in enumerate(candidates[start:]):
                path.append(num)
                dfs(path, tar - num, start + i)
                path.pop()

        dfs([], target, 0)
        return results
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/39-zu-he-zong-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.