Can a candidate number be used multiple times in Combination Sum?

Yes, each number can be chosen unlimited times, which is why backtracking needs to continue from the current index rather than moving forward.

How does pruning improve the backtracking performance?

Pruning stops recursion once the path sum exceeds the target, preventing exploration of invalid combinations and reducing time complexity.

Are the combinations in any specific order?

No, the problem allows returning combinations in any order as long as each combination itself reflects the correct counts of candidates.

What is the key failure mode in this problem?

A common failure is incorrectly handling repeated candidates or failing to backtrack properly, leading to missing or duplicated combinations.

How is the backtracking pattern applied in Combination Sum?

Backtracking explores each candidate recursively, reuses candidates as needed, and prunes paths exceeding the target to efficiently enumerate all valid combinations.

#39

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被选取。如果…

数组回溯

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

lightbulb

解题思路

方法一：排序 + 剪枝 + 回溯

我们可以先对数组进行排序，方便剪枝。

接下来，我们设计一个函数 $dfs(i, s)$ ，表示从下标 $i$ 开始搜索，且剩余目标值为 $s$ ，其中 $i$ 和 $s$ 都是非负整数，当前搜索路径为 $t$ ，答案为 $ans$ 。

在函数 $dfs(i, s)$ 中，我们先判断 $s$ 是否为 $0$ ，如果是，则将当前搜索路径 $t$ 加入答案 $ans$ 中，然后返回。如果 $s \lt candidates[i]$ ，说明当前下标及后面的下标的元素都大于剩余目标值 $s$ ，路径不合法，直接返回。否则，我们从下标 $i$ 开始搜索，搜索的下标范围是 $j \in [i, n)$ ，其中 $n$ 为数组 $candidates$ 的长度。在搜索的过程中，我们将当前下标的元素加入搜索路径 $t$ ，递归调用函数 $dfs(j, s - candidates[j])$ ，递归结束后，将当前下标的元素从搜索路径 $t$ 中移除。

在主函数中，我们只要调用函数 $dfs(0, target)$ ，即可得到答案。

时间复杂度 $O(2^n \times n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $candidates$ 的长度。由于剪枝，实际的时间复杂度要远小于 $O(2^n \times n)$ 。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                ans.append(t[:])
                return
            if s < candidates[i]:
                return
            for j in range(i, len(candidates)):
                t.append(candidates[j])
                dfs(j, s - candidates[j])
                t.pop()

        candidates.sort()
        t = []
        ans = []
        dfs(0, target)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the number of valid combinations and recursion depth, which is influenced by the target value and candidate magnitudes. Space complexity is driven by recursion stack depth and storage of all valid combinations.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you handle repeated use of candidates correctly.
question_mark
Observes whether you prune branches when the cumulative sum exceeds the target.
question_mark
Evaluates if you maintain the uniqueness of combinations without extra structures.

warning

常见陷阱

外企场景

error
Failing to prune when the path sum exceeds the target, causing unnecessary recursion.
error
Modifying the path in place without restoring it, leading to incorrect combinations.
error
Incrementing the index too early and missing valid repeated candidate combinations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit each candidate to be used at most once, changing the backtracking logic to increment the index after use.
arrow_right_alt
Return combinations in non-descending order and remove duplicates, requiring sorting and skipping duplicates.
arrow_right_alt
Find combinations whose sum is closest to a target without exceeding it, needing additional tracking of best sums.

help

常见问题

外企场景

继续练习

#40 组合总和 II #37 解数独 #46 全排列