关于c:5回溯算法

回溯算法（back tracking)实际上一个相似枚举的搜寻尝试过程，次要是在搜寻尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的门路。

能够了解为深度优先算法。
通过枚举各种类型，依据条件限度，失去符合条件的后果。

个别用于要求出所有可能的后果。例如排列组合等等。
回溯算法框架：

result = []def backtrack(门路, 抉择列表):    if 满足完结条件:        result.add(门路)        return    for 抉择 in 抉择列表:        做抉择        backtrack(门路, 抉择列表)        撤销抉择

以全排列为例：

给定一个不含反复数字的数组 nums ，返回其 所有可能的全排列 。你能够 按任意程序 返回答案。

int **ret = NULL;int ret_num = 0;int *array = NULL;int array_num = 0;int *used = NULL;void backtrack(int *nums, int numsSize, int index){    if(index == numsSize)    {        int *temp = malloc(sizeof(int) * numsSize);        memcpy(temp, array, sizeof(int) * numsSize);        ret[ret_num] = temp;        ret_num++;    }    else    {        for(int i =0; i < numsSize; i++)        {            if(used[i] == 1)                continue;            array[array_num] = nums[i];            array_num++;            used[i] = 1;            backtrack(nums, numsSize, array_num);//array num 其实就是遍历的深度。            used[i] = 0;            array_num--;        }    }}int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){    if(numsSize <= 0)    {        *returnSize = 0;        return ret;    }    ret_num = array_num = 0;    int total_num = 1;    for(int i = 1; i <= numsSize; i++)        total_num *= i;    used = malloc(sizeof(int) * numsSize);    memset(used, 0, sizeof(int) * numsSize);    ret = malloc(sizeof(int*) * total_num);    array = malloc(sizeof(int) * numsSize);    backtrack(nums, numsSize, 0);    *returnColumnSizes = malloc(sizeof(int) * total_num);    for(int i = 0; i < total_num; i++)        (*returnColumnSizes)[i] = numsSize;    *returnSize = total_num;    return ret;}

此处应用一个数组来示意数字是否曾经应用。每次抉择只抉择没有应用的数字。
重点是每次backtracking完当前，要复原现场，复原到backtracking的上一步，保障对下次抉择没有影响。

又如组合问题：

给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。你能够按 任何程序 返回答案。

int **ret = NULL;int ret_num = 0;int *array = NULL;int array_size = 0;long long  get_num(int n){    long long  num = 1;    for(int i =1; i <= n; i++)    {        num *= i;    }    return num;}void dfs(int *table, int n, int k, int deepth, int m)//m防止出现雷同的组合。{    if(deepth == k)    {        int *temp = malloc(sizeof(int) * k);        for(int i =0; i < k; i++)            temp[i] = array[i];        ret[ret_num] = temp;        ret_num++;    }    else    {        for(int i = m; i <= n; i++)        {            if(table[i] == 0)                continue;            array[array_size++] = i;            table[i] = 0;            dfs(table, n, k , array_size, i);//i防止出现反复的后果。            array_size--;            table[i] = 1;         }    }}int** combine(int n, int k, int* returnSize, int** returnColumnSizes){    ret_num = array_size = 0;    int *table = malloc(sizeof(int) * (n + 1));    table[0] = 0;    for(int i = 1; i <= n; i++)        table[i] = 1;    int num = get_num(n)/get_num(k)/get_num(n-k);    ret = malloc(sizeof(int *) * num);    array = malloc(sizeof(int) * k);    dfs(table, n, k, 0, 0);        *returnSize = ret_num;    *returnColumnSizes = malloc(sizeof(int) * num);    for(int i =0; i < num; i++)        (*returnColumnSizes)[i] = k;    free(table);    free(array);    return  ret;   }

同样的，应用一个数组来存储数据是否被抉择。
每次backtracking完当前要复原现场。
同时在组合过程中，为了防止出现雷同的数据，例如：1，2，3和3，2，1和1，3，2等状况。
先for循环中，须要跳过抉择过的数据，往后循环。