未备案网站,南京seo排名,做企业网站所需要的资料,asp网站搭建软件理论基础
回溯算法解决的问题
回溯法#xff0c;一般可以解决如下几种问题#xff1a; 组合问题#xff1a;N个数里面按一定规则找出k个数的集合 切割问题#xff1a;一个字符串按一定规则有几种切割方式 子集问题#xff1a;一个N个数的集合里有多少符合条件的子集 排列…理论基础
回溯算法解决的问题
回溯法一般可以解决如下几种问题 组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式 子集问题一个N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则全排列有几种排列方式 棋盘问题N皇后解数独等等
回溯算法的模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}77.组合
题目链接
https://leetcode.cn/problems/combinations/description/
题目描述 思路
刚开始的想法就是使用两层for循环暴力求解但是发现只能满足集合为 2 的情况如果 k 3,甚至更大的话就需要更多层的for循环所以这种方式不可行看了视频以后发现这种情况属于回溯方法的一种需要穷尽每一种情况所以需要用到回溯算法 再回顾一下回溯算法的模板请看第一部分 下边是本题的解题方案
本题的终止条件是集合的大小等于 k 的时候就将小集合添加到大集合当中并结束这个方法结束的时候会回到调用出也就是 trackback(n,k,i1);回到这里以后会继续执行下边的语句也就是 list1.remove(list1.size()-1);这里的意思就是将上一个给移除继续下一种可能的结果 list.add(new ArrayList(list1));这句要注意不能直接写成list.add(list1);这会破坏原有添加进去的元素必须新建一个列表然后将 list1作为参数传进去形成一个新的列表
class Solution {ListListInteger list new ArrayList();ListInteger list1 new ArrayList();public ListListInteger combine(int n, int k) {trackback(n,k,1);return list;}public void trackback(int n,int k,int start){if(list1.size()k){list.add(new ArrayList(list1));return;}for (int i start; i n; i) {list1.add(i);trackback(n,k,i1);list1.remove(list1.size()-1);}}
}
