找到所有选择，走不通则回溯
假定问题的解是一个向量(a1,a2,a3,...,an)，其中的每个元素ai都是问题的一个元素
步骤：
建立一个问题的部分解v=(a1,a2,...,ak)
若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能
若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能
算法改进：搜索剪枝
剪枝（pruning）可以帮助我们减少搜索空间，更快的找到解
剪枝的思想就是就是通过某种判断，避免一些不必要的遍历过程，就是如果发现此分支不可能找到最优解，就立刻回溯
剪枝的策略需要具体问题具体分析，这里不细讲
回溯法框架：
递归法
Backtrack(k,X[1...K-1]) if(k>n) output(X[1...N]) else for each element x in S(k): if(constraint(x,X[1...k-1])) X[k]=x backtrack(k+1,X[1...k])
迭代法
IterativeBacktrack() k=1 while k>0 while set S(k) is not empty get a new element x from set S(k) if(constraint(x,X[1,k-1])) X[k]=x if(solution(X)) output(X) else k++
