【算法笔记】组合

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法笔记】组合，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2570字，纯文字阅读大概需要4分钟。

内容图文

组合问题：

• 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

问题分析：

经典的纯组合问题，可判断为回溯问题，所有回溯问题都可以抽象为树结构，是在一棵树上的深度优先遍历，那么在这里我们先画出一个简单的树结构，再进一分析问题。

然后进行我们回溯的三个步骤：

• 回溯函数的终止条件
  从图中可以看出，回溯的终止条件也就是达到了树的根节点。
  在这道题目中，当我们从集合中选取到两元素时就到达了叶子节点，也就是题目的终止条件。
  所以需要一个数组来存放当前选取的元素，并且需要一个结果集来存放选取的子集，在这里我定义一个一维数组path来存放子集，一个二维数组result来存放全部的结果集。
  得到终止时的代码为：

  if(path.size()==k){
  	result.add(new ArrayList<Integer>(path));  //保存path子集，结束本次递归
      return;
   }
  

• 单层递归的过程
  一般来说这里有三个基本步骤：
  （1）for循环控制树的横向遍历
  （2）递归控制纵向遍历
  （3）最后进行回溯

  

  我们再来看看这个树形结构，通过for循环从左到右遍历，然后通过递归函数不断调用自己来进行纵向遍历，当遇到叶子节点时就返回；但是在每一层的递归都是从该元素过后的下一个元素开始选择，比如我们第一层递归选择了1，那么下一层递归只能选择2、3、4，所以在这里需要一个标志来判断下一层递归从哪个元素开始。
  代码为：

  //通过startIndex来记录下一层递归从下一个元素开始，即i+1
  for (int i=startIndex;i<=n;i++) {  
            path.add(i);   //存放节点
            backTracking(n, k, i + 1);   //递归，纵向遍历
            path.remove(path.size() - 1);  //回溯，删除最后一个节点
   }
  

• 确定递归函数的参数和返回值
  （1）参数：通过上面的分析，确定基本需要的参数有n，k和startIndex
  （2）返回值：void

整体代码

public class Combine {

    List<Integer> path=new ArrayList<>();   //子集
    List<List<Integer>> result=new ArrayList<>();  //结果集

    public List<List<Integer>> combine(int n, int k) {
      backTracking(n,k,1);
      return result;
    }
	
	//递归函数
    public void backTracking(int n, int k,int startIndex) {

         if(path.size()==k){
             result.add(new ArrayList<Integer>(path));   //保存path子集，结束本次递归
         }
         //通过startIndex来记录下一层递归从下一个元素开始，即i+1
         for (int i=startIndex;i<=n;i++) {
             path.add(i);//存放节点
             backTracking(n, k, i + 1); //递归，纵向遍历
             path.remove(path.size() - 1);//回溯，删除最后一个节点
         }
    }
}

剪枝操作

回溯法唯一提高效率的操作，顾名思义就是减掉一些没有必要的操作。
在本题中的例子中，如果起始元素为4，是完全没必要的操作，应为后面已经没有元素了，所以可以直接剪掉它。在这个例子中你可能没感觉到提升好多效率，但是很多其它例子中这种没必要进行的操作很多，所以进行剪枝是非常有必要的。

针对本题，也就是起始元素后的元素总数必须大于等于还需要的元素

• 已选元素：path.size()
• 还需元素：k-path.size()
• 最大开始位置：n-(k-path.size())+1
  for循环代码为：

  for (int i=startIndex;i<=n-(k-path.size())+1;i++) {
  	path.add(i);
  	backTracking(n, k, i + 1);
      path.remove(path.size() - 1);
  }
  

内容总结

以上是互联网集市为您收集整理的【算法笔记】组合全部内容，希望文章能够帮你解决【算法笔记】组合所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---