leetcode
leetcode 1 ~ 50
组合总和

组合总和

难度:

标签:

题目描述

给你一个 无重复元素 的整数数组 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

代码结果

运行时间: 80 ms, 内存: 14.8 MB

// Java Stream Solution
// 思路：使用 Stream 来处理集合和数组。虽然 Stream 主要用于数据处理，但我们可以通过递归和流的结合来实现问题的解法。
 
import java.util.*;
import java.util.stream.*;
 
public class SolutionStream {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return combinationSumHelper(candidates, target, 0);
    }
 
    private List<List<Integer>> combinationSumHelper(int[] candidates, int target, int start) {
        if (target == 0) {
            return Arrays.asList(new ArrayList<>());
        }
        if (target < 0) {
            return Collections.emptyList();
        }
        return IntStream.range(start, candidates.length)
                .mapToObj(i -> combinationSumHelper(candidates, target - candidates[i], i)
                        .stream()
                        .peek(combination -> combination.add(0, candidates[i]))
                        .collect(Collectors.toList()))
                .flatMap(List::stream)
                .collect(Collectors.toList());
    }
}

解释

方法:

这个题解采用了回溯算法的思路来解决问题。回溯算法通过递归的方式，在候选数字中做选择，直到找到目标和为 target 的所有组合。具体来说： 1. 首先定义一个用于保存结果的列表 ans。 2. 然后定义一个回溯函数 backtrack，它接受两个参数：当前选择的数字路径 path 和下一个可选数字的起始索引 start。 3. 在回溯函数中，首先计算当前选择数字的总和 s。如果总和等于 target，则将当前路径加入结果列表 ans 中。如果总和已经大于等于 target，则无需继续递归，直接返回。 4. 如果总和小于 target，则从 start 开始遍历 candidates 数组，对于每个数字，将其加入路径 path，然后递归调用 backtrack 函数，更新下一次选择的起始索引为当前索引 i，这样可以重复选择当前数字。 5. 在递归回溯完成后，需要将当前数字从路径 path 中移除，以便尝试其他的选择。 6. 最后，在主函数中调用 backtrack 函数，初始路径为空列表，起始索引为 0，得到所有可能的组合结果。

时间复杂度:

O(1)

空间复杂度:

O(target + n)

代码细节讲解

🦆
在回溯算法中，为什么在总和已经大于等于目标值时直接返回而不继续递归是合理的？
▷
在回溯算法中，当当前路径的数字总和已经等于或超过目标值target时，继续添加更多的数字只会使总和增加，因此不可能得到总和恰好为target的组合。此时直接返回可以避免无效的递归调用，从而提高算法效率。这种做法是基于问题的限定条件（即寻找总和等于target的组合）来优化递归过程的一个例子。
🦆
在回溯过程中，每次递归调用使用当前索引i作为新的起始索引，这种做法如何确保所有可能的组合都被探索到？
▷
使用当前索引i作为新的起始索引是为了允许组合中包含重复的数字，同时防止生成重复的组合。由于每次递归调用时，都是从当前索引i开始，这保证了从每个索引位置开始的所有可能的组合都被探索到。此外，它也确保了组合是按照非递减的顺序生成的，因此不会出现如[2,3]和[3,2]这样重复的组合，从而覆盖了所有可能的组合情况。
🦆
递归函数中使用的path.append操作后，为何可以直接在下一步递归调用中使用更新后的path，这样做的数据结构特性是什么？
▷
在Python中，列表（list）是一种可变的数据结构，其内容可以在不创建新实例的情况下被修改。当使用path.append操作时，实际上是在原有列表的基础上添加新的元素。递归调用中使用的是这个已经被修改的同一个列表对象。这种特性允许在递归过程中传递和修改同一个列表对象，从而有效地记录当前路径的状态而无需每次递归都创建新的列表。这样做减少了内存消耗并提高了程序的运行效率。
🦆
回溯算法完成后，如何确保结果列表中不包含重复的组合，尤其是在同一个数字可以无限制重复选择的情况下？
▷
在本题解中，由于回溯算法始终是从当前数字或之后的数字开始选择，这就保证了所有数字的选择顺序是一致的（即不会出现先选大后选小的情况）。这种策略自然而然地避免了生成重复的组合，因为每一种组合都是按照一定的顺序来创建的。此外，由于是从同一个索引或之后的索引开始递归，每次递归都是基于当前选择的路径，这进一步确保了组合的唯一性。因此，在这种策略下，结果列表中不会包含重复的组合，即使是在同一个数字可以无限制重复选择的情况下。

相关问题

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

 

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

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

 

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

 

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

 

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

 

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

 

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

因子的组合

因子的组合

组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

 

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

 

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

 

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

外观数列组合总和 II