组合
难度:
标签:
题目描述
给定两个整数 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 <= 201 <= k <= n
代码结果
运行时间: 416 ms, 内存: 16.2 MB
/* 思路：我们可以利用Java Stream和组合生成器来生成所有的组合。首先生成1到n的数组，接着使用Stream API来生成所有k长度的子集组合。 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<Integer> numbers = IntStream.rangeClosed(1, n).boxed().collect(Collectors.toList());
return combinations(numbers, k).collect(Collectors.toList());
}
private Stream<List<Integer>> combinations(List<Integer> numbers, int k) {
if (k == 0) {
return Stream.of(new ArrayList<>());
}
if (numbers.isEmpty()) {
return Stream.empty();
}
Integer first = numbers.get(0);
List<Integer> rest = numbers.subList(1, numbers.size());
Stream<List<Integer>> withFirst = combinations(rest, k - 1).map(l -> {
List<Integer> result = new ArrayList<>(l);
result.add(first);
return result;
});
Stream<List<Integer>> withoutFirst = combinations(rest, k);
return Stream.concat(withFirst, withoutFirst);
}
}
解释
方法:
这个题解使用了回溯算法。它从数字1开始，通过递归的方式枚举所有可能的组合。在递归函数中，如果当前路径的长度等于k，就将当前路径加入结果列表中。否则，从当前位置开始，依次将每个数字加入路径，并递归调用函数，直到找到所有的组合。在回溯过程中，需要将最后加入的数字从路径中移除，以便尝试其他的组合。
时间复杂度:
O(k * n^k)
空间复杂度:
O(k * C(n, k))
代码细节讲解
🦆
题解中提到了回溯算法，你是如何判断这种问题适合使用回溯算法而不是其他算法？
▷🦆
在进行回溯时，为什么选择从`start`索引开始循环而不是从0开始？这样做的目的是什么？
▷🦆
回溯算法中的递归函数`backtrack`为什么需要传入`path`和`start`两个参数？这两个参数具体起什么作用？
▷🦆
在回溯的过程中，每次递归调用后为什么要进行`path.pop()`操作？这一步操作的意义是什么？
▷相关问题
组合总和
给你一个 无重复元素 的整数数组 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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40