目录
一.题目描述
二.解题思路
三.回溯三部曲
3.1确定递归函数的返回值以及参数
3.2回溯算法的终止条件
3.3确定单层循环搜索逻辑
四.具体的代码
一.题目描述
给定两个整数 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]]
二.解题思路
本题为一道经典的回溯算法问题。
本题最直接的解法就是for循环的嵌套,比如当k取2时,这时大家都可以想到我们可以用两层for循环来解决这个问题
代码如下:
int n = 4;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
}
}
但是我们要考虑一个问题,那就是如果k = 50呢,那我们就要用50层for循环嵌套?
此时我们就要使用回溯算法来解决本题
回溯算法虽然也是一种暴力搜索的方法,但是我们可以使用递归来解决问题.
回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。
所以我们可以把本题抽象为如下树的结构:
可以看出这棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。
那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
三.回溯三部曲
3.1确定递归函数的返回值以及参数
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();path集合 用来存放符合条件结果的集合
result集合 用来存放结果集
3.2回溯算法的终止条件
如果组合数长度达到规定的k值就可以满足条件终止'
//如果组合数长度达到规定的k值就可以满足条件终止
if(path.size() == k){
//将满足条件的一维数组添加到结果集中
result.add(new ArrayList<>(path));
return;
}3.3确定单层循环搜索逻辑
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
//确定单层循环搜索逻辑
for (int i = startIndex; i <= n; i++) {
//处理节点
path.add(i);
//递归函数
backtracking(n,k,i+1);
//回溯操作(撤销)
path.removeLast();
}四.具体的代码
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Solution77 {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return result;
}
public void backtracking(int n , int k , int startIndex){
//确定终止条件
//如果组合数长度达到规定的k值就可以满足条件终止
if(path.size() == k){
//将满足条件的一维数组添加到结果集中
result.add(new ArrayList<>(path));
return;
}
//确定单层循环搜索逻辑
for (int i = startIndex; i <= n; i++) {
//处理节点
path.add(i);
//递归函数
backtracking(n,k,i+1);
//回溯操作(撤销)
path.removeLast();
}
}
public static void main(String[] args) {
Solution77 solution77 = new Solution77();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
List<List<Integer>> res = new ArrayList<>();
res = solution77.combine(n,k);
System.out.println(res);
}
}
