福永网站制作,如何利用互联网进行宣传推广,外贸网站怎么做促销,甘肃省最新消息今天回溯算法理论介绍
回溯算法是一种基于递归思想的算法设计技术#xff0c;适用于解决需要构造所有解或找到特定解的组合问题。回溯的基本思路是通过系统地搜索所有可能的解决方案#xff0c;然后逐步撤销不符合要求的选择#xff0c;回到上一步继续尝试。这种算法最适合应用…回溯算法理论介绍
回溯算法是一种基于递归思想的算法设计技术适用于解决需要构造所有解或找到特定解的组合问题。回溯的基本思路是通过系统地搜索所有可能的解决方案然后逐步撤销不符合要求的选择回到上一步继续尝试。这种算法最适合应用于决策树、排列组合、子集生成等涉及多阶段决策问题的场景。
如何理解回溯算法
回溯法解决的问题都可以抽象为树形结构是的我指的是所有回溯法的问题都可以抽象为树形结构
因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。
递归就要有终止条件所以必然是一棵高度有限的树N叉树。
回溯算法的一般结构
void backtrack(参数) {if (满足结束条件) {记录解或返回;}for (选择 in 可选择列表) {做出选择;backtrack(新的参数); // 递归调用继续做下一步选择撤销选择; // 撤销选择回到上一步的状态}
}剪枝套路
剪枝Pruning是一种优化回溯算法的技术用于在搜索过程中减小问题规模、提高效率从而避免不必要的计算。它的核心思想是在构造解决方案的过程中如果发现某些部分已经不能通向一个可行的解就可以提前结束这条路径的搜索直接“剪掉”这部分的搜索空间从而节省时间。
简单来说剪枝就是在回溯过程中“提前发现死胡同”然后立刻停止当前的搜索而不是继续探索下去。这样可以减少不必要的计算量极大地提高回溯的效率。
77.组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n
思路
最开始的思路就是按照回溯算法的模板写的这道题的目的是从范围 [1, n] 中选取 k 个数生成所有可能的组合并返回这些组合。解决这道题的有效方法是使用回溯算法。回溯的基本思路是逐步尝试所有可能的选择并通过递归进行深度优先搜索。在每次递归过程中我们依次选择一个新的数字加入当前组合如果当前组合的大小达到了 k就将其存储为一个有效解。在这之后我们会通过回溯撤销选择的方式返回到上一步尝试其他可能的选择从而确保找到所有的组合解。为了优化算法我们应用了剪枝策略即在递归过程中如果剩余的可选数字数量不足以组成完整的组合我们会提前终止当前路径从而减少不必要的计算提高效率。通过这种逐步尝试、回退、剪枝的过程最终生成并返回所有符合要求的组合。
解答
第一次尝试(超出内存范围)
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void travelback(int n,int k,int start,int* num,int combinesize,int*** result,int* returnSize,int** returnColumnSizes)
{if(combinesize k){(*returnSize);*result realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] malloc(sizeof(int)*k);for(int i 0;i k;i){(*result)[(*returnSize)-1][i] num[i];}*returnColumnSizes realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] k;return;}for(int i start;i n;i){num[combinesize] i;travelback(n,k,i1,num,combinesize1,result,returnSize,returnColumnSizes);}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {*returnSize 0;*returnColumnSizes NULL;int** result NULL;int* num malloc(sizeof(int)*k);travelback(n,k,1,num,0,result,returnSize,returnColumnSizes);return result;
}最终答案(gpt帮助)
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
long long factorial(int n) {long long result 1;for (int i 1; i n; i) {result * i;}return result;
}
int combinationCount(int n, int k) {return factorial(n) / (factorial(k) * factorial(n - k));
}
void travelback(int n, int k, int start, int* num, int combinesize, int** result, int* returnSize) {if (combinesize k) {for (int i 0; i k; i) {result[*returnSize][i] num[i];}(*returnSize);return;}for (int i start; i n; i) {num[combinesize] i;travelback(n, k, i 1, num, combinesize 1, result, returnSize);}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {*returnSize 0;int totalCombinations combinationCount(n, k);int** result malloc(totalCombinations * sizeof(int*));for (int i 0; i totalCombinations; i) {result[i] malloc(k * sizeof(int));}*returnColumnSizes malloc(totalCombinations * sizeof(int));for (int i 0; i totalCombinations; i) {(*returnColumnSizes)[i] k;}int* num malloc(k * sizeof(int));travelback(n, k, 1, num, 0, result, returnSize);free(num);return result;
}216.组合总和 |||
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。示例 2:
输入: k 3, n 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 2 6 9
1 3 5 9
2 3 4 9
没有其他符合的组合了。示例 3:
输入: k 4, n 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。提示:
2 k 91 n 60
思路
这道题与上面很像但是这道题多了一点条件所以我们在终止条件下要分成两个部分当它找的元素已经有要求的那么多个的时候我们对其进行检测如果最终结果等于它所要求的结果那么这是我们需要取得一个数组如果不是直接返回出去而我们在取值上面也有变化我们有一个变量叫做sum是用来进行计算总和的我们先把这个数值加上如果不满足的话我们又重新剪掉最终返回答案。
解答
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
void travelback(int k,int n,int start,int* num,int combinesize,int*** result,int* returnSize,int** returnColumnSizes,int sum)
{if(combinesize k){if(sum n){(*returnSize);*result realloc(*result,(*returnSize)*sizeof(int*));(*result)[(*returnSize)-1] malloc(sizeof(int)*k);for(int i 0;i k;i){(*result)[(*returnSize)-1][i] num[i];}*returnColumnSizes realloc(*returnColumnSizes,(*returnSize)*sizeof(int));(*returnColumnSizes)[(*returnSize)-1] k;}return;}for(int i start;i 9;i){sum i;num[combinesize] i;travelback(k,n,i1,num,combinesize1,result,returnSize,returnColumnSizes,sum);sum - i;}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {*returnSize 0;*returnColumnSizes NULL;int** result NULL;int* num malloc(sizeof(int)*k);int sum 0;travelback(k,n,1,num,0,result,returnSize,returnColumnSizes,sum);return result;
}17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
12 abc3 def4 ghi5 jkl6 mno7 pqrs8 tuv9 wxyz*0 -# ↑
示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
思路
解答
/*** Note: The returned array must be malloced, assume caller calls free().*/
void travelback(const char* digits, int* returnSize, const char** a, int index, char** result, char* num) {if (index strlen(digits)) {num[index] \0; result[(*returnSize)] malloc((strlen(num) 1) * sizeof(char)); strcpy(result[*returnSize], num);(*returnSize);return;}int digit digits[index] - 0;const char* letter a[digit];for (int i 0; i strlen(letter); i) {num[index] letter[i];travelback(digits, returnSize, a, index 1, result, num);}
}
char** letterCombinations(char* digits, int* returnSize) {const char* a[10] { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};if (digits NULL || strlen(digits) 0) {*returnSize 0;return NULL;}int len strlen(digits);int maxSize 1;for (int i 0; i len; i) {int digit digits[i] - 0;if (digit 2 digit 9) {maxSize * strlen(a[digit]);}}*returnSize 0;char* num (char*)malloc((len 1) * sizeof(char)); char** result (char**)malloc(maxSize * sizeof(char*));travelback(digits, returnSize, a, 0, result, num);free(num); return result;
}注意
num[index] \0’一定要放在最上面因为调用 malloc((strlen(num) 1) * sizeof(char)) 的时候num 并不是一个完整的字符串因为 num[index] \0; 还没有设置。strlen(num) 计算长度时会从 num 的开头开始寻找 \0但由于它还未设置因此 strlen(num) 可能返回一个不正确的长度值可能是过大或过小。
反思
今天的题目很有难度有些题目需要多次理解但是今天对于回溯算法有了一定的理解还需要多练。
