leetcode-77

LeetCode 77. 组合

1 题目描述

• 题目链接：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 <= 20
• 1 <= k <= n

2 思路

直接进行穷举，当k为2时，直接两层for循环就可以搞定。
但是，k值实际上是函数的输入，而k值决定了for循环的层数，因而这种思路无法用迭代来实现，考虑使用递归法。

• 由于每个值不能重复利用，因而上一层for循环就会决定下一层for循环的起始点，可以在函数参数表中创建一个用来存储循环起始索引，记为startindex。单层循环逻辑如下：

  for(int i = startIndex; i <= n; i++){
      tmp[cnt++] = i;
      backtracking(n, k, i+1, returnSize, tmp);
      cnt--;              //回溯
  }

• 函数返回的条件：采用一个暂存数组来记录当前遍历的数值，当暂存数组中的容量达到k时说明已经遍历完成，将暂存数组中的结果保存到结果数组中。逻辑如下：

if(cnt > k-1){
    ret[*returnSize] = (int *)malloc(sizeof(int)*k);
    for(int i = 0; i < cnt; i++){       //将结果保存下来
        ret[*returnSize][i] = tmp[i];
    }
    (*returnSize)++;
    return;                             //回溯
}

实际上我们可以对循环进行优化：由于题目是要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().
 */
int **ret, cnt = 0;
void backtracking(int n, int k, int startIndex, int *returnSize, int *tmp){
    if(cnt > k-1){
        ret[*returnSize] = (int *)malloc(sizeof(int)*k);
        for(int i = 0; i < cnt; i++){
            ret[*returnSize][i] = tmp[i];
        }
        (*returnSize)++;
        return;
    }else{
        for(int i = startIndex; i <= n - (k-cnt)+1; i++){   //剪枝
            tmp[cnt++] = i;
            backtracking(n, k, i+1, returnSize, tmp);
            cnt--;          //回溯
        }
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    int tmp[k];
    ret = (int **)malloc(sizeof(int*) * 10001);
    *returnSize = 0;
    backtracking(n, k, 1, returnSize, tmp);
    *returnColumnSizes = (int *)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i < (*returnSize); i++){
        (*returnColumnSizes)[i] = k;
    }
    return ret;
}

3 相似题目

• 39. 组合总和

  题目要求：找出一个数组中总和为目标值的组合，每个数字可无限制重复被选取，数组中数字各不相同，要求解集不能包含重复的组合。

• 40. 组合总和 II

  题目要求：找出一个数组中总和为目标值的组合，每个数字只能用一次，数组中数字可能相同，要求解集不能包含重复的组合。

• 216. 组合总和 III

  题目要求：在1-9数字中选取k个数使其总和为目标值，每个数字只能用一次，且解集不能包含重复的组合。

以上三题的思路都一样，只是函数返回的条件以及循环的条件需要进行处理而已。39和216中数字各不相同，代码基本一致；而40中数字可能相同，那么就需要对相同数字进行处理。

先进行排序，然后按”组合”问题的思路进行求解，在循环体中加入判断条件，如果当前值与上一个值相同，则没必要进行下一层的循环，直接跳到不同数字再进行下一层循环，逻辑如下：

for(int i = startIndex; i < n; i++){
    if(i>startIndex && candidates[i]==candidates[i-1{
        continue;   //相同数字的情况
    }
    tmp[cnt++] = candidates[i];
    sum += candidates[i];
    backtracking(candidates, n, target, i+1, returnSize, returnColumnSizes, tmp);
    cnt--;
    sum -= candidates[i];           
}