回溯法

回溯是一种通过做出选择、递归、然后在回溯时撤销选择来系统性地探索所有可能解决方案的方法。它是解决要求所有组合、所有排列、所有子集或任何有效配置的问题的正确工具。关键技能是识别何时剪枝：当你能够确定某个分支无法导向有效解决方案时提前停止该分支。没有剪枝，回溯就只是暴力搜索。这里的大多数问题共享相同的递归骨架，仅在决定有效选择和停止条件的约束上有所不同。