知识卡片

普通读书笔记卡 · 5654.c.4.c

排列选择集随路径使用量缩小

理解等级:中级

生成互异元素全排列时,路径表示已放定顺序,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