兰州专业网站建设团队,瑞安 网站建设培训,1m带宽做网站快不,视频网站很难建设吗目录
一、题目描述
二、整体思路
三、代码 一、题目描述
原题地址 二、整体思路 对于组合问题#xff0c;首先要想到回溯法。那么可以根据回溯法模版进行设计。
void backtrace(元素){if(满足题目要求的条件){保存目前路径/状态/结果;return;}for循环,往目前状态相邻的所…目录
一、题目描述
二、整体思路
三、代码 一、题目描述
原题地址 二、整体思路 对于组合问题首先要想到回溯法。那么可以根据回溯法模版进行设计。
void backtrace(元素){if(满足题目要求的条件){保存目前路径/状态/结果;return;}for循环,往目前状态相邻的所有可能的状态进行遍历{往下一个状态去的所需要进行的操作;backtrace(下一个状态);//递归调用backtrace;回溯操作,还原成目前状态。}} 理解回溯法的本质是穷举所有可能的状态,通过递归来使得可以在原状态的基础上进入下一个状态也就是入栈。那么不停地入栈直到没有可进入的状态时,递归函数进行出栈。 那么函数出栈时,我们需要把当前状态还原成原状态因为之前进入的下一个状态随着出栈已经结束了。
三、代码 class Solution {ListListInteger resnew ArrayList();ListInteger tempnew ArrayList();public ListListInteger combinationSum3(int k, int n) {backtrace(1,k,n);return res;}void backtrace(int l,int k,int n){//l表示遍历到的数,n表示距离相差之和还有多远if(temp.size()k){if(n0){res.add(new ArrayList(temp));//不要直接用temp,因为temp是引用,如果直接用temp回溯时会改变temp,res里面的元素也会改变}return;}for(int il;i9;i){//所有可能的状态就是1-9temp.add(i);backtrace(i1,k,n-i);temp.remove(temp.size()-1);}return;}
}
