数码电子产品网站名称,重庆建设工程造价网官网,建设部网站一级开发资质,专业制作行驶证题目 思路 先找出数组中最小元素#xff0c;与目标数比较#xff1a; 若目标数小#xff0c;则无组合可能#xff1b; 若相等#xff0c;则输出该最小元素#xff1b; 若目标数大#xff0c;则寻找一元素的组合可能#xff0c;寻找二元素的组合可能 以candidates [2,3…题目 思路 先找出数组中最小元素与目标数比较 若目标数小则无组合可能 若相等则输出该最小元素 若目标数大则寻找一元素的组合可能寻找二元素的组合可能 以candidates [2,3,6,7], target 7为例 27找一元素组合可能7 找两元素组合可能25的组合数34的组合数61的组合数 7的组合可能7223232322 找5的组合数25 5的组合可能2332 找一元素组合可能[ ] 找二元素组合可能23的组合数32的组合数 找3的组合数23 3的组合可能3 找一元素组合可能3 找二元素组合可能21的组合数 找1的组合数21 找2的组合数22 2的组合可能2 找4的组合数24 4的组合可能22 找一元素组合可能[ ] 找二元素组合可能22的组合数 找2的组合数22 2的组合可能2 找1的组合数21 1的组合可能[ ] 完全没办法排除加法的交换律... 官方思路回溯剪枝 知识补充 回溯的本质是穷举【算法】回溯算法_codecapture的博客-CSDN博客 常用来解决 组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式 子集问题N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则全排列的排列方式个数 棋盘问题N皇后解数独等等 概括的说就是能解决抽象为N叉树的各种问题方法是在集合中递归查找子集其中集合的大小等于树的宽度递归的次数等于树的深度 回溯算法的模板为void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}比较参考博客里和上面描述的推导过程发现是在找两元素组合可能时出错导致同一组合重复出现所以在确定两元素组合中的某一元素后应该对组合数的集合范围进行修改 再次推导以candidates [2,3,6,7], target 7为例 27找一元素组合可能7 找两元素组合可能25的组合数[2,3,6,7]34的组合数[3,6,7]61的组合数 [6,7] 7的组合可能7223 找5的组合数[2,3,6,7]25 5的组合可能23 找一元素组合可能[ ] 找二元素组合可能23的组合数[2,3,6,7]32的组合数[3,6,7] 找3的组合数[2,3,6,7]23 3的组合可能3 找一元素组合可能3 找二元素组合可能21的组合数[2,3,6,7] 找1的组合数[2,3,6,7]21 找2的组合数[3,6,7]32 2的组合可能[ ] 找4的组合数[3,6,7]34 4的组合可能[ ] 找一元素组合可能[ ] 找二元素组合可能31的组合数[3,6,7] 找1的组合数31 1的组合可能[ ] 找1的组合数 [6,7]61 1的组合可能[ ] 解题过程
//是错误的代码
def backtracking(candidates, num, out, index):
//candidates待选列表 num目标值 out输出列表 index第几层用于控制到根节点时切换保存列表if min(candidates) num:out.pop()elif min(candidates) num:out.append(min(candidates))else:for i in range(len(candidates)):new candidates[i:]new_v num - candidates[i]if new_v 0:breakelif new_v 0:out.append(candidates[i])breakelse:index index 1out.append(candidates[i])backtracking(new, new_v, out, index)index - 1if index 1:total_out.append(out)out * 0return
题解中的办法
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:# 回溯无重复元素根据剩余值凑成目标ans []path []candidates.sort() # 预先排序# 收集逻辑为target 0def backtracking(index,path,target):if index len(candidates) or target 0:return if target 0: # 收集条件ans.append(path[:])return for i in range(index,len(candidates)): # 注意可以重复收集 path.append(candidates[i]) # 做选择backtracking(i,path,target-candidates[i])path.pop() # 取消选择backtracking(0,[],target)return ans作者菜狗阿笨-暂告一段落
链接https://leetcode.cn/problems/Ygoe9J/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 总结 按照再次推导的思路写代码时发现因为多层循环的嵌套和多个判别条件导致不会对结果进行保存和删除只能一遍遍调试 调试了得有一两个小时发现变量作用域和我以为的不一样即用等号赋值的操作会被解释成创建一个局部变量 局部变量全局变量“index index - 1”“index - 1”out[ ]out *0 以及在2-3-[3,6,7]k2和3-3-[3,6,7]k1时需要pop的次数不同因为2-3-[3,6,7]k2的另一分叉数上存在2-2-3的父节点2 题解中的办法就是标准的回溯模板需要学习不要自己造各种判断条件
