关于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 循环中，须要跳过抉择过的数据，往后循环。