回溯算法练习day.4

93.复原ip地址

链接：. - 力扣（LeetCode）

题目描述：

有效 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 中的任何数字。你可以按任何顺序返回答案。

示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
提示：

1 <= s.length <= 20
s 仅由数字组成

思路：

因为是分割问题，因此可以使用回溯算法解决，我们可以将其抽象为一个树形结构

因为IP地址总共只有3个.，因此我们可以使用一个标记来记录逗点的数量，当逗点足够三个时，我们就不再需要向下遍历，因为再向下就已经不是合法的IP地址了，我们在这时候只需要对剩余的字符串进行判断，如果剩余的字符串是合法的，我们就将其进行收集，并插入逗点，这样就得到了一个合法的IP地址

代码如下：

// 记录结果数组
char** result;
// 结果数组的当前元素数量
int resultTop;
// 记录应该加入'.'的位置的数组
int segments[3];// 判断字符串片段是否有效
int isValid(char* s, int start, int end) {// 若起始位置大于结束位置，则不合法if(start > end)return 0;// 如果数字以0开头并且不止一位，则不合法if (s[start] == '0' && start != end) {return false;}int num = 0;// 遍历字符串片段，将字符转换为数字，并判断是否大于255for (int i = start; i <= end; i++) {// 遇到非数字字符，则不合法if (s[i] > '9' || s[i] < '0') {return false;}num = num * 10 + (s[i] - '0');// 如果数字大于255，则不合法if (num > 255) {return false;}}return true;
}// 回溯函数，用于生成符合条件的 IP 地址
void backTracking(char* s, int startIndex, int pointNum) {// 若'.'数量为3，分隔结束if(pointNum == 3) {// 若最后一段字符串符合要求，将当前的字符串放入结果数组中if(isValid(s, startIndex, strlen(s) - 1)) {// 分配临时字符串数组的内存空间，长度为原字符串长度加上最多3个'.'和一个结束符'\0'char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);int j;// 记录添加字符时tempString的下标int count = 0;// 记录添加字符时'.'的使用数量int count1 = 0;for(j = 0; j < strlen(s); j++) {tempString[count++] = s[j];// 若'.'的使用数量小于3且当前下标等于'.'下标，添加'.'到数组中if(count1 < 3 && j == segments[count1]) {tempString[count++] = '.';count1++;}}tempString[count] = 0;// 扩容结果数组，并将临时字符串添加到结果数组中result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));result[resultTop++] = tempString;}return ;}int i;// 从起始位置开始遍历字符串for(i = startIndex; i < strlen(s); i++) {if(isValid(s, startIndex, i)) {// 记录应该添加'.'的位置segments[pointNum] = i;// 递归调用自身，搜索下一个'.'的位置backTracking(s, i + 1, pointNum + 1);}else {break;}}
}// 主函数，入口点，用于恢复 IP 地址
char ** restoreIpAddresses(char * s, int* returnSize){// 分配结果数组的初始内存空间result = (char**)malloc(0);resultTop = 0;// 调用回溯函数，生成符合条件的 IP 地址backTracking(s, 0, 0);// 将结果数量存储到returnSize指针指向的变量中*returnSize = resultTop;// 返回结果数组return result;
}

78.子集

链接：. - 力扣（LeetCode）

题目描述：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集

（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

思路：

因为这题也是求组合问题，因此还是使用回溯算法解决，我们将其抽象为树形结构

就可以发现，树的每个节点都是我们需要收集的子集，注意，我们在第一条支路中取了1，在后边就不需要的取1了，因此第一条支路向下递归搜索取能够取到12,13等，如果在后面的支路中再取前面取过的元素，就会出现21,31等，因为是组合，因此这两个是重复的，所以不需要再进行取值

回溯实现：

1.确定函数参数和返回值：回溯返回值一般为空，传入的参数应该为题目提供的集合以及我们每次遍历的开始位置

2.确定函数的终止条件：当我们每条支路的开始遍历位置已经为空时，即我们已经遍历到了末尾，就到达了叶子节点，就进行返回

3.确定单层递归逻辑，收集路径下的节点，再向下递归，之后再进行回溯，遍历另一条支路

代码实现：

int *path;               // 存储当前路径的数组
int pathtop;             // 当前路径的顶部索引int **result;            // 存储所有子集的数组
int resulttop;           // 存储数组的顶部索引int *len;                // 存储每个子集的长度void copy()
{int *temp = (int *)malloc(sizeof(int) * pathtop);  // 临时数组，用于复制当前路径for(int i = 0; i < pathtop; i++)                   // 复制当前路径到临时数组temp[i] = path[i];result = (int **)realloc(result, sizeof(int *) * (resulttop + 1)); // 重新分配存储子集的数组大小len = (int *)realloc(len, sizeof(int) * (resulttop + 1)); // 重新分配存储子集长度的数组大小len[resulttop] = pathtop;                          // 存储当前子集的长度result[resulttop++] = temp;                        // 将当前子集添加到结果数组中
}void backtracking(int *nums, int numsSize, int startindex)
{copy();                                            // 复制当前路径到结果数组中if(startindex >= numsSize )return;for(int i = startindex; i < numsSize; i++){path[pathtop++] = nums[i];                    // 将当前元素添加到路径中backtracking(nums, numsSize, i+1);             // 递归调用，查找以当前元素开头的所有子集pathtop--;                                     // 回溯，移除最后添加的元素} 
}int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {path  = (int *)malloc(sizeof(int) * numsSize);     // 初始化路径数组result = (int **)malloc(sizeof(int *));            // 初始化存储子集的数组len = (int *)malloc(sizeof(int) * 1000);           // 初始化存储子集长度的数组resulttop = pathtop = 0;                           // 初始化路径顶部索引和结果顶部索引为0backtracking(nums, numsSize, 0);                   // 开始回溯查找所有子集*returnSize = resulttop;                           // 设置返回的子集个数*returnColumnSizes = (int *)malloc(sizeof(int) * resulttop); // 为每个子集的长度分配内存for(int i = 0; i < resulttop; i++)(*returnColumnSizes)[i] = len[i];              // 存储每个子集的长度return result;                                     // 返回所有子集数组
}

90.子集II

链接：. - 力扣（LeetCode）

题目描述：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的

子集

（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

思路：

该题与上题一样，也是求组合问题，但是这个题要求不能包含重复子集，因为我们要进行去重操作，可以考虑到使用回溯算法解决，所以可以抽象为一个树形结构

我们可以看出，当我们横向出现重复的元素时，得到的结果就会重复，因此就需要在横向进行去重操作，而在纵向，因为我们取出的是集合中不同位置的元素，因此就不需要去重，在这里，我们收集的也是每个节点的结果，只是增加了去重的操作

回溯实现：

1.确定函数的参数和返回值，参数应该为题目提供和集合和开始遍历的位置

2.确定终止条件，当我们遍历到叶子节点，即开始位置已经是集合末尾时，退出

3.确定单层递归逻辑，当我们在遍历时，只要横向不重复，就进行收集路径，并进行递归和回溯，如果发现重复，则跳过

注意：我们应该在终止条件之前进行结果的收集，因为那是新的递归遍历的开始，每次开始前我们都应该对上次递归的结果进行收集，因为上次的结果是我们的节点

代码实现：
/*** 返回大小为 *returnSize 的数组的数组。* 数组的大小作为 *returnColumnSizes 数组返回。* 注意：返回的数组和 *columnSizes 数组都必须是通过 malloc 分配的，假设调用者会调用 free()。*/int *path; // 路径数组
int pathtop; // 路径长度int **result; // 结果数组
int resulttop; // 结果数组的长度int *len; // 每个子集的长度数组// 比较函数，用于排序数组
int cmp(const void *a, const void *b)
{return *((int *)a) - *((int *)b);
}// 复制当前路径并添加到结果数组中
void copy(void)
{int *temp = (int *)malloc(sizeof(int) * pathtop);for (int i = 0; i < pathtop; i++)temp[i] = path[i];result = (int **)realloc(result, sizeof(int *) * (resulttop + 1));len = (int *)realloc(len, sizeof(int) * (resulttop + 1));len[resulttop] = pathtop;result[resulttop++] = temp;
}// 回溯函数，用于递归生成所有子集
void backtracking(int *nums, int numsSize, int startindex, int *used)
{copy(); // 复制当前路径if (startindex >= numsSize)return;for (int i = startindex; i < numsSize; i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)continue; // 避免重复元素path[pathtop++] = nums[i];used[i] = 1;backtracking(nums, numsSize, i + 1, used);used[i] = 0;pathtop--;}
}// 主函数，生成所有不重复的子集
int **subsetsWithDup(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{path = (int *)malloc(sizeof(int) * numsSize);len = (int *)malloc(sizeof(int) * 1000);int *used = (int *)malloc(sizeof(int) * numsSize);pathtop = resulttop = 0;qsort(nums, numsSize, sizeof(int), cmp); // 排序输入数组backtracking(nums, numsSize, 0, used); // 从第一个元素开始生成子集*returnSize = resulttop;*returnColumnSizes = (int *)malloc(sizeof(int) * resulttop);for (int i = 0; i < resulttop; i++)(*returnColumnSizes)[i] = len[i];return result; // 返回生成的子集数组
}