LeetCode算法题解

题解"/>

LeetCode算法题解

题目链接：77. 组合

题目描述：

给定两个整数 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

算法分析：

利用回溯算法。

首先创建一个二位数组来存放所有组合，窗建一个一维数组来存放每种组合。

然后通过递归（递归传入的参数为横向遍历的起始位置startIndex）和回溯来遍历所有可能的组合；

递归结束条件：当前组合的长度等于k的时候将组合存放到结果集当中，然后返回。

如果不满足结束条件，那么用for循环横向遍历组合的每个元素(从startIndex开始），将当前元素插入组合，然后递归去执行下一层情况（是否插入下一个元素或者满足条件，将组合放入结果集），递归完之后要将组合中的当前元素删除（因为这种情况已经通过递归遍历完了），然后执行下一层for循环。

代码如下：

class Solution {List<List<Integer>>result = new ArrayList<>(new ArrayList<>());//创建一个二维数组来存放所有路径的集合int N;int K;//将n、k定义到全局区域List<Integer>list = new ArrayList<Integer>();//定义一个一维数组用来存放每个组合public void backTravel(int startIndex) {//递归传入的参数为横向遍历的起始位置if(list.size() == K ) {//如果当前组合的长度等于k，将当前组合存放到结果集当中result.add(new ArrayList<>(list));return;}for(int i = startIndex; i <= N - K + list.size() + 1; i++) {//横向遍历list.add(i);//将当前元素放到组合中，backTravel(i + 1);//递归去存放下一个元素list.remove(list.size() - 1);//回溯，删除当前元素，在开始下一层for循环}}public List<List<Integer>> combine(int n, int k) {N = n;K = k;backTravel(1);return result;}
}

总结

回溯算法，有个纵向遍历（递归遍历，就像遍历二叉树的深度）和横向遍历（for循环遍历，就像遍历二叉树的宽度）。

回溯算法的模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}