回溯算法之组合 Posted on 2021-06-27 00:00:00 2021-06-28 00:00:00 by Author 摘要 给定一个数n和一个数k,你能找出从1到n中所有的k个数的组合吗???????? # 回溯算法---组合 1. 题目描述 - 给定两个整数 *n* 和 *k*,返回 1 ... *n* 中所有可能的 *k* 个数的组合。 2. 示例描述 - 示例一 - 输入: n = 4, k = 2 - 输出: ``` [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] ``` - 示例二 - 输入:n=6, k=3 - 输出: ``` [ [1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4], [1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6], [2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6], [2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6] ] ``` 3. 解题思路 - 从本题开始,就要进入回溯算法章节,其实这个回溯思想也不是什么新的知识,在二叉树章节中几乎用递归遍历的方式时都牵扯了回溯思想,只是那一章节主要就是讲二叉树操作的问题,没有具体针对的讲回溯算法。本题就是一道实实在在的用回溯思想解决的一道题目。 - 首先回溯算法简单说白了就是一种暴力解法,就是暴力搜索所有符合条件的结果。其实现与递归分离不开。它的一般实现形式在我个人理解有五步:第一步确定递归出口(满足题目要求的结果的时候,就结束),第二步确定遍历的集合(因为回溯递归是暴力搜索,肯定在一个集合中去暴力搜索,所有说每次递归的时候结果集可能改变,也有可能不变,这时候就要确定遍历的集合了)。第三步记录本层递归的 值(因为用暴力递归形式搜索,每次递归的时候可能时结果集的一小步,所有记录下来,当本层下所有递归执行完成后,满足结果的就会被加入结果集中)。第四步继续调用递归函数(执行本层下其余集合的递归方式,找到满足要求的结果),第五步回溯,移除本层加入的结果(因为递归函数调用后会有回溯到本层调用的结束位置,这时本节点以及处理完成,所以要移除这个节点,便于其余节点的递归操作,别忘了本节点也在循环里。),直到整个集合都递归搜索完成,那么暴力搜索也就完成了。最终结果集中就存放满足要求的结果。 - 本题就是按照以上步骤去实现的,具体实现逻辑如下,并且每步都进行解释,大家可以根据题解以及代码慢慢理解这个回溯思想。 4. 代码示例 ```java //定义最终结果结合、集合中每个元素又是一个集合,也就是1到n中的k个数的集合 //最终1到n的所有k个数的集合的集合就是最终结果 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { //调用递归回溯算法。 trackBack(n,k,1,new ArrayList<>()); return result; } //算法的参数定义为什么是这样的呢 //首先前两个参数不用说了,就是题目的参数 //后面两个参数解释一下(index参数,就是本层循环到哪个数了,这个数就是控制递归函数持续向下搜索的遍历,直到底层为止,就结束本层递归) //最后一个参数就是记录递归过程中,所到达的节点,并且也是最终结果集合的子集的记录者 public void trackBack(int n ,int k,int index,List<Integer> tempResult){ //递归条件出口,结果集合中的个数与k相等,说明找到一组,就返回,以便后续继续寻找满足条件的结果 if(tempResult.size() == k){ result.add(new ArrayList<>(tempResult)); return; } //寻找遍历的结果结合 //为什么不从1开始尼,从index开始尼,因为从1开始的话,即会出现重复的集合,并且会出现自己和自己组合的情况(不满足条件) //这里举个栗子n=2,k=2的话如果从index每次从1开始就会出现[1,1],[1,2],[2,1],[2,2]但是实际结果只有[1,2] //这里达到去重的效果, for (int i =index;i<=n;i++){ //加入本层的节点 tempResult.add(i); //继续递归本层下面的其他节点 trackBack(n,k,i+1,tempResult); //回退到本层,移除本层加入结果集中的节点,以便可以继续遍历其他节点,这样达到回溯的思想 tempResult.remove(tempResult.size()-1); } } ```
{{ item.content }}
{{ child.content }}