- 我最近开了几个专栏，诚信互三！
====> |||《算法专栏》：：刷题教程来自网站《代码随想录》。|||
====> |||《C++专栏》：：记录我学习C++的经历，看完你一定会有收获。|||
====> |||《Linux专栏》：：记录我学习Linux的经历，看完你一定会有收获。|||
====> |||《C#专栏》：：记录我复习C#的经历，深度理解，查漏补缺，不定期更新。|||
回溯算法
- 什么是回溯
- 回溯算法能解决什么问题
- 回溯算法经典OJ
什么是回溯
回溯是一种暴力搜索的算法，回溯算法通过循环控制树的宽度，递归调用控制树的深度，来收集满足条件的集合。
回溯算法能解决什么问题
1.排列组合
2.组合总和
3.分割字串
4.子集
回溯算法经典OJ
1.排列组合问题
组合问题的分析：组合及每层选的值以及该值的左边所有值下一层则不能在被选择，为了控制选值，则需要startIndex来索引下标，并根据条件收集和返回结果。
排列问题的分析：排列问题每层都可以取除了上一层选择的值之外的所有值，所以一般不需要startIndex控制索引，而需要hash表记住上一层所选择的值。
剪枝：剪枝操作要根据题目的收集结果条件进行剪枝，一般都在for循环的判断部分进行剪枝。
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
问题分析：该题要求返回组合，则需要startIndex控制索引防止重复选取，同时返回条件是当收集到2个结果返回。
int* result;// - 结果数组
int arrTop;// - 控制返回数组的下标
int top;// - 控制结果数组的下标
int** arr;// - 结果数组
void BackTracking(int n, int k, int** arr, int index)
{
if(top == k)// - 满足条件返回
{
int* tmp = (int*)malloc(sizeof(int)*k);
for(int i = 0; i < k; i++)
{
tmp[i] = result[i];
}
arr[arrTop++] = tmp;
return;
}
for(int i = index; i <= n; i++)
{
result[top++] = i;
BackTracking(n,k,arr,i+1);
// - 回溯
top--;
}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes)
{
arr = (int**)malloc(sizeof(int*)*10000);
result = (int*)malloc(sizeof(int)*k);
arrTop = top = 0;
BackTracking(n,k,arr,1);
*returnSize = arrTop;// - 返回arr数组有多少行
*returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));// - 返回arr数组每列有多少个元素。
for(int i = 0; i < *returnSize; i++)
{
(*returnColumnSizes)[i] = k;
}
return arr;
}
剪枝：本题要求收集到k个值就返回，若接下来收集的元素最大值都收集不到k个，则就不用遍历了。
result数组中有Top个元素，所需需要的元素个数为: k - Top;
列表中剩余元素（n-i） >= 所需需要的元素个数（k - Top)
在集合n中至多要从该起始位置 : i <= n - (k - Top) + 1，开始遍历
for(int i = index; i <= n - (k-Top)+1; i++)
全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
问题分析：不含重复数子，则代表不存在两个结果相同，但是所对应的下标不同，则不需要在每层去重，要返回全排列，返回条件就是rTop的值是numsSize，并且该问题为排列问题，可以重选。
int* path;
int pathTop;
int** ans;
int ansTop;
//将used中元素都设置为0
void initialize(int* used, int usedLength) {
int i;
for(i = 0; i < usedLength; i++) {
used[i] = 0;
}
}
//将path中元素拷贝到ans中
void copy() {
int* tempPath = (int*)malloc(sizeof(int) * pathTop);
int i;
for(i = 0; i < pathTop; i++) {
tempPath[i] = path[i];
}
ans[ansTop++] = tempPath;
}
void backTracking(int* nums, int numsSize, int* used)
{
//若path中元素个数等于nums元素个数，将nums放入ans中
if(pathTop == numsSize) {
copy();
return;
}
int i;
for(i = 0; i < numsSize; i++) {
//若当前下标中元素已使用过，则跳过当前元素
if(used[i])
continue;
used[i] = 1;
path[pathTop++] = nums[i];
backTracking(nums, numsSize, used);
//回溯
pathTop--;
used[i] = 0;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//初始化辅助变量
path = (int*)malloc(sizeof(int) * numsSize);
ans = (int**)malloc(sizeof(int*) * 1000);
int* used = (int*)malloc(sizeof(int) * numsSize);
//将used数组中元素都置0
initialize(used, numsSize);
ansTop = pathTop = 0;
backTracking(nums, numsSize, used);
//设置path和ans数组的长度
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = numsSize;
}
return ans;
}
2.组合总和问题
组合总和问题的分析：组合及每层选的值以及该值的左边所有值下一层则不能在被选择，为了控制选值，则需要startIndex来索引下标，并根据条件收集和返回结果。
剪枝：剪枝操作要根据题目的收集结果条件进行剪枝，组合总和问题一般通过排序+和下一层的元素相加来剪枝，一般都在for循环的判断部分进行剪枝。
组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
问题分析：该问题为组合问题，数字为1-9，则代表数字有序，要收集相加和为n的k个整数集合，则不满足这个条件直接返回。
int* result;
int rTop;
int aTop;
void BackTracking(int k, int n, int startIndex, int sum, int** arr)
{
// - 剪枝
if(rTop == k)
{
if(sum == n) {
int* tempPath = (int*)malloc(sizeof(int) * k);
int j;
for(j = 0; j < k; j++)
tempPath[j] = result[j];
arr[aTop++] = tempPath;
}
return;
}
// - 剪枝
else if(rTop != k && sum >= n)
{
return;
}
for(int j = startIndex; j <=9; j++)
{
sum+=j;
result[rTop++] = j;
BackTracking(k,n,j+1,sum,arr);
rTop--;
// - 组合总和问题要注意每层回溯要-=结果数组内容。
sum-=j;
}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes)
{
int** arr = (int**)malloc(sizeof(int*)*1000);
//初始化辅助变量
result = (int*)malloc(sizeof(int) * k);
rTop = aTop = 0;
BackTracking(k, n, 1, 0,arr);
//设置返回的二维数组中元素个数为ansTop
*returnSize = aTop;
//设置二维数组中每个元素个数的大小为k
*returnColumnSizes = (int*)malloc(sizeof(int) * aTop);
int i;
for(i = 0; i < aTop; i++) {
(*returnColumnSizes)[i] = k;
}
return arr;
}
剪枝：该题依旧对数量有限制，则可以用组合问题的剪纸方法进行剪枝
for(int i = index; i <= 9 - (k-Top)+1; i++)
组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
问题分析：该问题为组合问题，同一个数子课重复使用，找出和为target的值。
int** arr;
int* result;
int rTop;
int aTop;
int* length;
void BackTracking(int sum, int target, int* candidates, int n, int startIndex)
{
// - sum > target返回
if(sum > target)
return;
// - 等于target收集数据
if(sum == target)
{
int* tmp = (int*)malloc(sizeof(int)*rTop);
for(int i = 0; i < rTop; i++)
{
tmp[i] = result[i];
}
arr[aTop] = tmp;
length[aTop++] = rTop;
return;
}
// - 改题目需要的是组合，所以不用遍历遍历过的
for(int j = startIndex; j < n; j++)
{
sum+=candidates[j];
result[rTop++] = candidates[j];
BackTracking(sum,target,candidates,n,j);
rTop--;
// - sum 要-;
sum-=candidates[j];
}
}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
{
length = (int*)malloc(sizeof(int)*200);
arr = (int**)malloc(sizeof(int*)*1000);
result = (int*)malloc(sizeof(int)*100);
rTop = aTop = 0;
int sum = 0;
BackTracking(sum, target,candidates,candidatesSize,0);
*returnSize = aTop;
*returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
int i;
for(i = 0; i < aTop; i++) {
(*returnColumnSizes)[i] = length[i];
}
return arr;
}
剪枝：只要某一层的和+下一层将要遍历的数大于target就不再进入循环。
for (int i = startIndex; i < n && sum + candidates[i] <= target; i++)
3.分割字串问题
分割字串问题的分析：**分割字串问题的本质在于选择分割位置，我们通过startIndex控制分割的起始位置，循环变量控制分割位置，分割过的位置不能在分割，会出现重复。
分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
问题分析：该问题为分割字串问题，同时收集结果的条件为全部回文，[startIndex,i]是一个分割区间，只要整个串被分割完，则代表可以收集结果了。
char*** arr;
char** result;
int aTop;
int rTop;
int* arrSize;
// - 判断回文
int checkStr(char* s, int start, int end)
{
while(start <= end)
{
if(s[start] == s[end])
{
start++;
end--;
}
else
{
return 0;
}
}
return 1;
}
char* curStr(char* s, int start, int end)
{
char* tmp = (char*)malloc(sizeof(char)*(end-start+2));
int index = 0;
for(int i = start; i <= end; i++)
{
tmp[index++] = s[i];
}
tmp[index] = '\0';
return tmp;
}
void copy()
{
char** tmp = (char**)malloc(sizeof(char*)*rTop);
for(int i = 0; i < rTop; i++)
{
tmp[i] = result[i];
}
arrSize[aTop] = rTop;
arr[aTop++] = tmp;
}
void BackTracking(char* s, int len, int startIndex)
{
// startIndex >= strlen的时候收集结果
if(startIndex >= len)
{
copy();
return ;
}
for(int j = startIndex; j < len; j++)
{
if(checkStr(s,startIndex,j))
{
result[rTop++] = curStr(s,startIndex,j);
}
// - 某层不回文，则++接着判断。
else
continue;
BackTracking(s,len,j+1);
rTop--;
}
}
char*** partition(char* s, int* returnSize, int** returnColumnSizes)
{
arrSize = (int*)malloc(sizeof(int)*40000);
arr = (char***)malloc(sizeof(char**)*40000);
int len = strlen(s);
// - result数组存储的是满足条件的组合，该组合不会超过len个
result = (char**)malloc(sizeof(char*)*len);
rTop = aTop = 0;
BackTracking(s,len,0);
*returnSize = aTop;
*returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
for(int i = 0; i < aTop; i++)
{
(*returnColumnSizes)[i] = arrSize[i];
}
return arr;
}
复原IP地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
问题分析：本题目为分割字串问题，分割条件为加每个ip地址都是有效，且要加入点号。
char* result;
char** arr;
int rTop;
int aTop;
int isIPAdders(char* s, int start, int end)
{
if(start > end)
return 0;
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return 0;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return 0;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return 0;
}
}
return 1;
}
void CurStr(char* s, int start, int end)
{
for(int i = start; i <= end; i++)
{
result[rTop++] = s[i];
}
}
void BackTracking(char* s, int len, int startIndex, int pointSize)
{
if(pointSize == 3)
{
if(isIPAdders(s, startIndex, len-1))
{
char* tmp = (char*)malloc(sizeof(char)*(len+4));
CurStr(s, startIndex, len-1);
for(int i = 0; i <= rTop; i++)
{
tmp[i] = result[i];
}
tmp[rTop] = '\0';
arr[aTop++] = tmp;
// - 最后一次回退不能由循环完成，必须在这里完成，并且最后一个回退不用回退.号
rTop-=((len-1)-startIndex+1);
return;
}
return;
}
// - 每个合法地址从startIndex开始最多3个字符，剪枝。
for(int j = startIndex; j < 3+startIndex; j++)
{
if(isIPAdders(s,startIndex, j))
{
CurStr(s,startIndex,j);
result[rTop++] = '.';
pointSize++;
BackTracking(s,len,j+1,pointSize);
rTop-=(j-startIndex+2);
pointSize--;
}
// - 只要起始位置不是合法地址，则该串就无法分割出合法地址。
else
break;
}
}
// - 分割子串
char** restoreIpAddresses(char* s, int* returnSize)
{
int len = strlen(s);
if(len < 4 && len > 12)
return NULL;
arr = (char**)malloc(sizeof(char*)*10000);
result = (char*)malloc(sizeof(char)*(len+4));
rTop = aTop = 0;
BackTracking(s,len,0,0);
*returnSize = aTop;
return arr;
}
剪枝：每个分割项的数字个数是[1-3]，所以可以在for循环判断部分剪枝。
for(int j = startIndex; j < 3+startIndex; j++)
4.子集问题
子集问题的分析：子集问题的本质依旧是组合问题，不过收集条件为无，及收集所有结点，同时每次收集完不用返回。
子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
问题分析：本题为子集问题，则要收集所有结点。
int** arr;
int* result;
int* length;
int rTop;
int aTop;
void copy()
{
int* tmp = (int*)malloc(sizeof(int)*10);
for(int i = 0; i < rTop; i++)
{
tmp[i] = result[i];
}
length[aTop] = rTop;
arr[aTop++] = tmp;
}
// - 子集问题--收集所有回溯树的结点
void BackTracking(int* nums, int numsSize, int startIndex)
{
copy();
// - 没有元素可取，就返回。
if(startIndex >= numsSize)
return;
for(int i = startIndex; i < numsSize; i++)
{
result[rTop++] = nums[i];
BackTracking(nums,numsSize, i+1);
rTop--;
}
}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
arr = (int**)malloc(sizeof(int*)*2000);
result = (int*)malloc(sizeof(int)*numsSize);
length = (int*)malloc(sizeof(int)*2000);
rTop = aTop = 0;
BackTracking(nums,numsSize,0);
*returnSize = aTop;
*returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
for(int i = 0; i < aTop; i++)
{
(*returnColumnSizes)[i] = length[i];
}
return arr;
}
递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
问题分析：存在重复元素，并且要求返回不同递增子序列，则不能通过排序去重，可以使用hash表，记录每次选择的元素，完成去重操作，去重的原因在于重复的元素存在重复收集结果的情况，同时改题目也需要我们遍历所有结点，收集结果的条件是result数字的元素大于1。
int** arr;
int* result;
int* length;
int rTop;
int aTop;
void copy()
{
int* tmp = (int*)malloc(sizeof(int)*rTop);
// for(int i = 0; i < rTop; i++)
// {
// tmp[i] = result[i];
// }
memcpy(tmp, result, rTop*sizeof(int));
length[aTop] = rTop;
arr[aTop++] = tmp;
}
find(int* hash, int size, int element)
{
int i;
for(i = 0; i < size; i++) {
if(hash[i] == element)
return 1;
}
return 0;
}
// - 去重 - 不能用排序进行去重，因为要求原数组的递增子序列 -- 哈希表
void BackTracking(int* nums, int numsSize, int startIndex)
{
if(rTop > 1)
copy();
// - 每层都生成一个哈希表，去重。
int* hash = (int*)malloc(numsSize*sizeof(int));
int hashTop = 0;
for(int i = startIndex; i < numsSize; i++)
{
// - 满足以下条件++，不收集结果。
if((rTop > 0 && nums[i] < result[rTop-1]) || find(hash, numsSize,nums[i]))
continue;
result[rTop++] = nums[i];
hash[hashTop++] = nums[i];
BackTracking(nums,numsSize, i+1);
rTop--;
}
}
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
arr = (int**)malloc(sizeof(int*)*33000);
result = (int*)malloc(sizeof(int)*numsSize);
length = (int*)malloc(sizeof(int)*33000);
rTop = aTop = 0;
BackTracking(nums,numsSize,0);
*returnSize = aTop;
*returnColumnSizes = (int*)malloc(sizeof(int)*aTop);
for(int i = 0; i < aTop; i++)
{
(*returnColumnSizes)[i] = length[i];
}
return arr;
}
