知识卡片
同层去重与路径占用分开
有重复值的排列中,selected约束当前路径是否已使用某个输入位置;duplicated约束这一层的候选循环是否已尝试过相同值。前者随回溯恢复,后者在本层循环内保留,防止重复分支。
两个作用域不可混用。原书backtrackII递归时误调用backtrackI,会让后续层失去同层去重,应理解为继续调用带去重的II;不能把原代码当已经正确去重。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
每一轮选择中开启一个哈希表duplicated ,用于记录该轮中已经尝试 过的元素,并将重复元素剪枝: // === File: permutations_ii.go === /* 回溯算法:全排列 II */ func
参考来源
- 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[27901,28011))
- 结论依据:实际II结构、两种剪枝对比及错误递归目标支持。
- 原始内容:每一轮选择中开启一个哈希表duplicated ,用于记录该轮中已经尝试 过的元素,并将重复元素剪枝: // === File: permutations_ii.go === /* 回溯算法:全排列 II */ func