多合一建网站,备案网站到期了怎么办,网站运营策划是什么,问卷调查网站怎么做原题出于leetcode第77题https://leetcode.cn/problems/combinations/ 1.树型结构 2.回溯三部曲 递归函数的参数和返回值 确定终止条件 单层递归逻辑
3.代码
二维数组result
一维数组path
void backtracking(n,k,startindex){if(path.sizek){result.append(path);return ;}…原题出于leetcode第77题https://leetcode.cn/problems/combinations/ 1.树型结构 2.回溯三部曲 递归函数的参数和返回值 确定终止条件 单层递归逻辑
3.代码
二维数组result
一维数组path
void backtracking(n,k,startindex){if(path.sizek){result.append(path);return ;}for(istartindex;in;i){path.push(i);backtracking(n,k,i1);path.pop(); }return ;
}4.剪枝算法长度为k时的剪枝
由于要求组合的长度为k故若遍历到某个数时其后面刚好有k-1个数则这个数即为应当遍历的最后一个数。如下图树型结构所示 可以在遍历时对i的范围进行调整调整逻辑如下 首先我们要知道当前选取了多少个元素即path.size() 其次计算还需要选取多少个元素k-path.size() 假设此时取到的数为x则还未取的数的范围是[x,n]故有
n-x1k-path.size()
解得xn-(k-path.size)1
所以i的取值到n-(k-path.size)1即可具体代码如下
二维数组result
一维数组path
void backtracking(n,k,startindex){if(path.sizek){result.append(path);return ;}for(istartindex;in-(k-path.size)1;i){path.push(i);backtracking(n,k,i1);path.pop(); }return ;
}文章中有关树型结构的图片出自代码随想录这是一个非常好的算法平台强烈推荐学算法的同学看一看
