c语言数据结构回溯算法题之组合

img

img


给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。
如
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
这个图片是解题代码，但是不理解，如果有1.2.3.4这4个数，两两组合，在代码第一次调用我可以理解为什么1.2会出来，但是后面就不懂了，还有自减

在函数 func 中，首先判断当前已经在 temp 数组中的数字个数是否达到 k，如果达到就输出一组组合结果，然后返回。
 
如果 tempSize 不足 k，就将当前数字 cur 放入 temp 数组中，使用 tempSize 记录已经放入的数字个数，并递归调用 func 函数。接着，取出 temp 数组中最后一个数字，tempSize 减一，撤销上一步的操作，即当前数字不放入 temp 数组中，再递归调用 func 函数。
 
这样，就能够通过回溯算法，遍历所有可能的组合，找出所有满足条件的组合。
 
在主函数中，给定了参数 n 和 k，并以此作为调用 func 函数的起始参数。
 

img


最近更新

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 你可以看下这个问题的回答https://ask.csdn.net/questions/7559726
  • 你也可以参考下这篇文章：计算正整数n中的第k位数字
  • 除此之外, 这篇博客: 【第43题】左移的应用 | 给定 n 和 k，问 n 的二进制表示第 k 位 是否是 1中的 零、前言 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

      目前本专栏正在进行优惠活动，在博主主页添加博主好友（好友位没有满的话），可以获取 付费专栏优惠券。

  • 以下回答来自chatgpt:

    回溯算法解题思路：

    回溯算法是一种解决问题的方法，它从解决问题的每一步开始，逐步构建一个完整的解决方案。对于组合问题，每一步可以选择当前位置的元素或不选择，直到选定k个数，这个时候就得到了一个组合。接下来，再在剩下的数中进行选择，直到得到所有可能的组合。具体实现可以通过递归函数或栈来实现。

    组合问题C语言实现：

    以下是使用递归函数实现的C语言代码，其中将k个数的组合存储在res数组中，backtrack函数用于回溯，在每一步中判断是否达到了目标k个数，如果是就将当前组合加入res数组中，否则进行下一步选择或回退操作。

    void backtrack(int* nums, int numsSize, int k, int start, int* track, int trackSize, int** res, int* returnSize, int** returnColumnSizes) {
    if (trackSize == k) {
        res[*returnSize] = (int*)malloc(sizeof(int) * k);
        memcpy(res[*returnSize], track, sizeof(int) * k);
        (*returnColumnSizes)[*returnSize] = k;
        (*returnSize)++;
        return;
    }
    for (int i = start; i < numsSize; i++) {
        track[trackSize] = nums[i];
        backtrack(nums, numsSize, k, i + 1, track, trackSize + 1, res, returnSize, returnColumnSizes);
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    int** res = (int**)malloc(sizeof(int*) * 10000);
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int) * 10000);
    int* nums = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    int* track = (int*)malloc(sizeof(int) * k);
    backtrack(nums, n, k, 0, track, 0, res, returnSize, returnColumnSizes);
    return res;
}

    自减运算符用途和流程解释：

    自减运算符“--”用于使一个变量减1，其作用相当于使用“-=”操作符。在C语言中，“--”运算符有两种形式：前缀和后缀。前缀形式将变量减1之后再返回该变量本身，即--变量名；后缀形式是先返回该变量的值，再进行减1操作，即变量名--。在组合问题C语言实现代码中，判断k是否达到目标，实现方式是将k自减1，即k--。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^