知识卡片
排列选择集随路径使用量缩小
生成互异元素全排列时,路径表示已放定顺序,selected[i]表示第i个输入是否在当前路径中。选择后标true并加入,递归返回后同时恢复标志和路径长度。
这是同一路径不可重复使用同一元素的约束,不是全局禁止该元素出现在其他排列。全部n!个解若每个复制n项,还需n乘n!级输出工作,不能只计调用栈空间。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
selected[i] 表示 choices[i] 是否已被选择,并基于它实现以下剪枝操作。 ‧ 在做出选择choice[i] 后,我们就将selected[i] 赋值为True ,代表它已被选择。 ‧ 遍历选择列表ch
参考来源
- 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[26261,26371))
- 结论依据:实际排列树及backtrackI配对更新,说明路径级范围与输出成本。
- 原始内容:selected[i] 表示 choices[i] 是否已被选择,并基于它实现以下剪枝操作。 ‧ 在做出选择choice[i] 后,我们就将selected[i] 赋值为True ,代表它已被选择。 ‧ 遍历选择列表ch