知识卡片

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

有重复值的组合只跳同层重复

理解等级:中级

已排序输入中,同一层循环若当前值与前一值相等,且它不是本层第一个候选,就跳过这条等价分支。条件i>start使下一层仍能合法使用另一个同值元素。

若简单禁止所有相邻相等值,会漏掉由两个不同输入位置组成的合法组合。每个位置只用一次通过下一层从i+1开始保证,去重与次数限制是两项不同约束。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      if i > start && (*choices)[i] == (*choices)[i-1] { continue } // 尝试:做出选择,更新 target, start *state = append(*sta

    参考来源

    - 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[2509,2619)) - 结论依据:实际subsetSumII排序/同层相邻条件/递归i+1,保留作用范围。 - 原始内容:if i > start && (*choices)[i] == (*choices)[i-1] { continue } // 尝试:做出选择,更新 target, start *state = append(*sta