回溯代码框架

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
  // 判断是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
    // 不再继续搜索
    return;
  }
  // 遍历所有选择
  for (Choice choice : choices) {
    // 剪枝：判断选择是否合法
    if (isValid(state, choice)) {
      // 尝试：做出选择，更新状态
      makeChoice(state, choice);
      backtrack(state, choices, res);
      // 回退：撤销选择，恢复到之前的状态
      undoChoice(state, choice);
    }
  }
}

例子1

演示代码

例子2

演示代码