题解"/>
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(路径,选择列表); // 递归回溯,撤销处理结果}
}
更多推荐
LeetCode算法题解
发布评论