backtracking(回溯)

回溯法，是通过递归的方式穷举组合问题的所有可能解，关于这个问题的解决方法大致有如下步骤

• 建立解矩阵，如果不知道可行解数量(有待探索)，可以建立动态存储数据结构
• 构建基本问题，首先检查解结构完备与否，如果完备返回解，或者记录解结构，另外如果存在提前结束的可能，可以贪婪的检查当前解结构是否已经违反解规则，如果是则提前结束
• 基本问题的迭代结构，对于一般的组合问题，这个迭代的维度可能保持一致，当然也可能不一致，主要取决于原始问题的结构特征;每一次迭代需要进一步完备解结构，并且递归的进行下一步完备，值得注意的是：我们需要判断当前操作对横向和纵向的影响，如果是在解数量上（如是否有重复解等的）的影响，则需要在当前函数结构下对组合空间进行约束，如减少或者跳过重复项的选择;如果是在解结构上(比如解结构中不能出现重复的选择)的影响，则需要在递归调用之前改变约束组合空间，在递归之后释放约束。
  下面举例说明：

1. permutation问题

排列问题是一类典型的可以用backtracking解决的问题，给定n个数字（或者字），打印出所有可能的排列。数学上我们知道这个数量是一个阶乘，很好理解就是n次无放回的选择，这个操作结构如何在用backtracking实现呢？
按照回溯的思路：

solution[n!] //建立一个全局变量，当然也可以不这样做，只是需要在函数递归调用时不断传递解容器和当前解
void backtrack(current_solution, index){
if(current_solution is well_generated)
       print it or record it
       return
else if current_solution is bad_structure
       return // backtrack的迭代函数一般都是无返回值的
for index to space_size
       add space[index] to current_solution
       backtrack(current_solution, index+1)

如果给定一个初始的排列(结构中可能含有重复元素)，此时可能会存在重复的解，原因在于横向空间中的重复会导致最终生成完全一致的解，并且递归的重复，所以必须在每一层次上改善解空间(不能对纵向产生影响)，即记录已经迭代过的元素，避免重复！但是我们知道在解结构中是可能存在重复元素的，这时我们需要纵向的控制解结构，即通过记录已经构造的解中重复元素的数量来避免破坏解结构。下面的代码是个很好的例子：

    int  array [ 128 ];  //个别存入128个ASCII字元的出现次数
    char  solution [ MAX ];
     
    void  permutation ( int  k ,  int  n )
    {
        if  ( k  ==  n )
        {
            for  ( int  i = 0 ;  i < n ;  i ++)
                cout  <<  solution [ i ];
            cout  <<  endl ;
            return ;
        }
        
        for  ( int  i = 0 ;  i < 128 ;  i ++)    //列举每一个字母
            if  ( array [ i ] >  0 )        //还有字母剩下来，就要列举
            {
                array [ i ]--;          //用掉了一个字母
                
                solution [ k ] =  i ;     // char变数可以直接存入ascii数值
                permutation ( k + 1 ,  n );
     
                array [ i ]++;          //回收了一个字母
            }
    }

2. next permutation
   相邻元素比较大小，直到前一元素小于后一元素，用遍历过的最小元素代替当前停止元素，然后将其他元素逆序输出。
3. 有效括号最大长度
   下标存储法，通过记录下标来标记相邻的最大有效字串
4. 字符串匹配问题一开始应该考虑用组合动态规划去解，考虑能否对0行和0列做初始化，如果能够初始化，则问题多半就能解决，一种求字符串之间距离的算法值得借鉴