给定两个整数+n+和+k,返回范围+[1,+n]+中所有可能的+k+个数的组合。你可以按+任何顺序+返回答案。 例如: 输入:n+=+4,+k+=+2 输出: [ ++[2,4], ++[3,4],
时间: 2023-10-06 07:12:16 浏览: 88
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
解决这个问题的一种方法是使用回溯法和DFS。我们可以创建一个结果列表 res,一个临时列表 list,以及一个递归函数 dfs。在 dfs 函数中,我们首先判断如果 count 等于 k,那么就将 list 添加到 res 中。然后,我们遍历从 start 到 n 的所有数字,将数字添加到 list 中,并递归地调用 dfs 函数。最后,我们将 list 中最后一个元素移除,以便尝试下一个数字。
以下是解决这个问题的Java代码实现:
```java
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
if (n < 1 || k < 1) return res;
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = i + 1;
}
List<Integer> list = new ArrayList<>();
dfs(num, k, 0, 0, list);
return res;
}
public void dfs(int[] num, int k, int count, int start, List<Integer> list) {
if (count == k) {
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i < num.length; i++) {
list.add(num[i]);
dfs(num, k, count + 1, i + 1, list);
list.remove(list.size() - 1);
}
}
}
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)