本文主要是介绍【代码随想录】【算法训练营】【第24天】 [77]组合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
思路及算法思维,指路 代码随想录。
题目来自 LeetCode。
day 23,愉快的周五~
题目详情
[77] 组合
题目描述
77 组合
解题思路
前提:组合求子集问题
思路:回溯算法三部曲:递归函数的返回值以及参数、回溯函数终止条件、单层搜索的过程。
重点:回溯算法是一种暴力求解,常常会超出时间限制,需要剪枝操作。
回溯法,一般可以解决如下几种问题:
组合问题:N个数里面按一定规则找出k个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等等
代码实现
C语言
未剪枝的回溯
/*** 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 backtracking(int n, int k, int startIndex, int *nums, int *numsSize, int **ans, int *returnSize, int **returnColumnSizes)
{if (*numsSize == k){// 找到一个组合(*returnColumnSizes)[(*returnSize)] = k;ans[(*returnSize)] = (int *)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){ans[(*returnSize)][i] = nums[i];} (*returnSize)++;return ;}// 未剪枝for (startIndex; startIndex <= n; startIndex++){nums[(*numsSize)] = startIndex;(*numsSize)++;// 递归backtracking(n, k, startIndex + 1, nums, numsSize, ans, returnSize, returnColumnSizes);// 回溯(*numsSize)--;nums[(*numsSize)] = 0;}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {int **ans = (int **)malloc(sizeof(int *) * 200000);*returnSize = 0;*returnColumnSizes = (int *)malloc(sizeof(int) * 200000);int nums[n];int numsSize = 0;backtracking(n, k, 1, nums, &numsSize, ans, returnSize, returnColumnSizes);return ans;
}
使用realloc会出现“内存超出限制”报错,原因未知~
剪枝的回溯
/*** 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 backtracking(int n, int k, int startIndex, int *nums, int *numsSize, int **ans, int *returnSize, int **returnColumnSizes)
{if (*numsSize == k){// 找到一个组合(*returnColumnSizes)[(*returnSize)] = k;ans[(*returnSize)] = (int *)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){ans[(*returnSize)][i] = nums[i];} (*returnSize)++;return ;}// 剪枝for (startIndex; startIndex <= (n - (k - (*numsSize)) + 1); startIndex++){nums[(*numsSize)] = startIndex;(*numsSize)++;// 递归backtracking(n, k, startIndex + 1, nums, numsSize, ans, returnSize, returnColumnSizes);// 回溯(*numsSize)--;nums[(*numsSize)] = 0;}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {int **ans = (int **)malloc(sizeof(int *) * 200000);*returnSize = 0;*returnColumnSizes = (int *)malloc(sizeof(int) * 200000);int nums[n];int numsSize = 0;backtracking(n, k, 1, nums, &numsSize, ans, returnSize, returnColumnSizes);return ans;
}
今日收获
- 回溯算法三部曲:递归函数的返回值以及参数、回溯函数终止条件、单层搜索的过程;
- 剪枝操作。
这篇关于【代码随想录】【算法训练营】【第24天】 [77]组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!