大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、问题描述
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
二、问题分析
这道题是典型的backtracking类题目，这类题目感觉起来有点枚举的感觉（把所有的情况列出来）。这类题有类似的处理方式，可以参看generate parentheses，有回溯的基本解释。
三、Java AC 代码
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> item = new ArrayList<Integer>();
if (k > n || n <= 0 || k <= 0) {
return res;
}
dfsHelper(res, item, 1, n, k);
return res;
}
public void dfsHelper(List<List<Integer>> res, List<Integer> item,
int start, int n, int k) {
if (item.size() == k) {
res.add(new ArrayList<Integer>(item));
return;
}
for (int i = start; i <= n; i++) {
item.add(i);
dfsHelper(res, item, i+1, n, k);
item.remove(item.size() - 1);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/191636.html原文链接：https://javaforall.net
