首页 > 其他分享 >leetcode-19-回溯-组合问题(剪枝、去重)

leetcode-19-回溯-组合问题(剪枝、去重)

时间:2024-06-30 20:56:41浏览次数:22  
标签:剪枝 19 起始 元素 个数 path leetcode size

引自代码随想录

一、[77]组合

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

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

1、大致逻辑

 k为树的深度,到叶子节点的路径即为一个结果

开始索引保证不重复取数(从当前位置往后取值)

每一个节点为一个for循环

2、剪枝(优化)

(1)和大于n,结束递归。

(2)剩余元素不足以满足k(k个元素)

剩下所需元素:k-path.size()

 至多从该起始位置开始遍历(否则元素个数不够):n - (k - path.size()) + 1

为什么有个+1呢,因为包括起始位置(从起始位置开始遍历)

我们要是一个左闭的集合(重要!!!!)

path.size() : 已经找的个数
k-path.size() :还需找的个数

[x, n]的数组长度起码应该是k-path.size()才有继续搜索的可能

那么 n-x+1 = k-path.size()

解方程得 x = n+1 - (k-path.size()),

而且这个x是可以作为起点往下搜的

也就是for(i = s; i<=x; i++) 这里的x是可以取到的

类似题目[216]、[17](有点难度)、[39]、[40](需要对开始索引做处理)

标签:剪枝,19,起始,元素,个数,path,leetcode,size
From: https://blog.csdn.net/weixin_44925711/article/details/140023860

相关文章

  • Leetcode 3203. Find Minimum Diameter After Merging Two Trees
    Leetcode3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路2.代码实现题目链接:3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历,不断地删除已访问的叶子节点,并加入......
  • CF 1968 F. Equal XOR Segments (*1800) 思维
    CF1968F.EqualXORSegments(*1800)思维题意:给你一个长度为\(n\)的数组,如何可以把数组分成\(k(k>1)\)组,并且使得每组的异或和相等,那么这个数组就是完美的。现在给你\(q\)组询问,每次给你\(l,r\)。请你判断\(a_l\)到\(a_r\)之间是否是完美的。思路:对于每次询问......
  • 【解题报告】「NOI 1995」石子合并
    一个圆形操场上摆放\(n\(1\len\le100)\)堆石子。现要将\(n\)堆石子合并成一堆,每次只能选相邻的\(2\)堆合并成新的一堆,代价为新的一堆的石子数。求将\(n\)堆石子合并成一堆的最小代价和、最大代价和。“最大代价和”的转移证明\(\color{blue}{\text{结论}}\):对于\(......
  • C语言 | Leetcode C语言题解之第188题买卖股票的最佳时机IV
    题目:题解:intmaxProfit(intk,int*prices,intpricesSize){intn=pricesSize;if(n==0){return0;}k=fmin(k,n/2);intbuy[k+1],sell[k+1];memset(buy,0,sizeof(buy));memset(sell,0,sizeof(sell));......
  • C语言 | Leetcode C语言题解之第187题重复的DNA序列
    题目:题解:#defineMAXSIZE769/*选取一个质数即可*/typedefstructNode{charstring[101];intindex;structNode*next;//保存链表表头}List;typedefstruct{List*hashHead[MAXSIZE];//定义哈希数组的大小}MyHashMap;List*......
  • LeetCode 502 IPO All In One
    LeetCode502IPOAllInOneIPOdifficulty:Hard/难度:困难solutionshttps://leetcode.com/problems/ipo/description/?envType=daily-question&envId=2024-06-15demos//export{};functionprintSubArrays(arr,start=0,end=0){//Stopifwe......
  • LeetCode11. 盛最多水的容器题解
    LeetCode11.盛最多水的容器题解题目链接:https://leetcode.cn/problems/container-with-most-water示例思路暴力解法定住一个柱子不动,然后用其他柱子与其围住面积,取最大值。代码如下:publicintmaxArea1(int[]height){intn=height.length;intans=0;......
  • CF1979E Manhattan Triangle
    题目描述给定\(n\)个点,找出三个点使得这三个点两两之间的曼哈顿距离为偶数\(d\)\[n\le300000\]题解与一个点的曼哈顿距离为\(d\)的点是一个斜\(45°\)的正方形设这个点坐标为\((x,y)\)考虑另外两个点可能在哪些位置,如果另外两个点在正方形的同一条边上,那么这两个点的横纵......
  • 纯真IP库查询方法(2024-6-19更新qqwry.dat后无法查询,修改代码)
    2024-6-19更新qqwry.dat后使用pthon38那篇文章里的代码无法查询,使用pythom2的代码,修改之后python3可用,将文件放到工程里查询,不用Lib库里的。修改后的qqwry.py如下,python3可用。coding=utf-8forPython2.7为https://pypi.python.org/pypi/qqwry-py3的Python2版版本:2017-10-......
  • AI大模型企业应用实战(19)-RAG应用框架和解析器
    1开源解析和拆分文档第三方工具去对文件解析拆分,将文件内容给提取出来,并将我们的文档内容去拆分成一个小的chunk。常见的PDFwordmarkdown,JSON、HTML。都可以有很好的一些模块去把这些文件去进行一个东西去提取。1.1优势支持丰富的文档类型每种文档多样化选择与开源框......