组合

C++ 解法, 执行用时: 17ms, 内存消耗: 2360KB, 提交时间: 2022-05-05

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param k int整型
     * @return int整型vector<vector<>>
     */
    void backtracking(int n, int m, int k, vector<int>& temp,
                      vector<vector<int>>& result) {
        if (temp.size() == m) {
            result.push_back(temp);
            return;
        }
        for (int i = k; i <= n; i++) {
            temp.push_back(i);
            backtracking(n, m, i + 1, temp, result);
            temp.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        // write code here
        vector<vector<int>> result;
        vector<int> temp;
        backtracking(n, k, 1, temp, result);
        return result;

    }
};

C++ 解法, 执行用时: 17ms, 内存消耗: 2364KB, 提交时间: 2022-04-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型vector<vector<>>
     */
       void backtracking(int n,int m,int k,vector<int> &temp,vector<vector<int>> &result)
    {
        if(temp.size() == m)
        {
            result.push_back(temp);
            return;
        }
        for(int i = k;i <= n;i++)
        {
            temp.push_back(i);
            backtracking(n,m,i+1,temp,result);
            temp.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        // write code here
            vector<vector<int>> result;
    vector<int> temp;
    backtracking(n,k,1,temp,result);
    return result;

    }
};

C 解法, 执行用时: 18ms, 内存消耗: 1940KB, 提交时间: 2022-07-04

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param k int整型
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int** res;
static int* path;
//计算组合数的情况，给数组开辟合适的空间
int C(int n, int k) {
    if (n < 1 || k < 0 || k > n) return -1;
    if (k == 0) return 1;
    int molecule = 1, denominater = 1;
    for (int i = 0; i < k; i++) {
        molecule *= n - i;
        denominater *= i + 1;
    }
    return molecule / denominater;
}

void dfs(int start, int* length, int n, int k,
         int depth) {
    if (depth == k) {
        int* path_copy = (int*)malloc(k * sizeof(int));
        for (int i = 0; i < k; i++) {
            path_copy[i] = path[i];
        }
        res[(*length)++] = path_copy;//res长度加一
        return;
    }
    for (int i = start; i <= n; i++) {
        path[depth] = i;
        //元素不够结束循环 递归
        if ((depth + 1) + (n - i) < k) {
            return;
        }
        dfs(i + 1, length, n, k, depth + 1);
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes ) {
    // write code here
    //returnColumnSizes就是每一个一维数组的长度，话说不都是k吗
    int res_len = C(n, k);

    res = (int**) malloc(res_len * sizeof(int*));
    *returnSize = 0; //res长度置0
    path = (int*)malloc(k * sizeof(int));
    dfs(1, returnSize, n, k, 0);

    *returnColumnSizes = (int*)malloc(res_len * sizeof(int));
    for (int i = 0; i < res_len; i++) {
        *(*returnColumnSizes + i) = k;
    }
    return res;
}

C 解法, 执行用时: 19ms, 内存消耗: 2060KB, 提交时间: 2022-06-26

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param k int整型 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int num[21] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 };

void dfs(int index, int n, int k, int tmp[k], int tmpIndex, int*** result, int** returnColumnSizes, int* returnSize, int *maxResultSize) {
    if (tmpIndex == k) {
        if (*returnSize >= *maxResultSize) {
            (*maxResultSize) += 10;
            *result = (int **)realloc(*result, sizeof(int *) * (*maxResultSize));
            *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int) * (*maxResultSize));
        }
        
        int *subResult = (int *)malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++) {
            subResult[i] = tmp[i];
        }
        (*result)[*returnSize] = subResult;
        (*returnColumnSizes)[*returnSize] = k;
        (*returnSize) += 1;
        
        return;
    } else if (n - index < k - tmpIndex) {
        return;
    }
    
    tmp[tmpIndex] = num[index];
    dfs(index+1, n, k, tmp, tmpIndex + 1, result, returnColumnSizes, returnSize, maxResultSize);
    
    dfs(index+1, n, k, tmp, tmpIndex, result, returnColumnSizes, returnSize, maxResultSize);
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes ) {
    int maxResultSize = 10;
    int **result = (int **)malloc(sizeof(int *) * maxResultSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * maxResultSize);
    *returnSize = 0;
    
    int tmp[k];
    dfs(0, n, k, tmp, 0, &result, returnColumnSizes, returnSize, &maxResultSize);
        
    return result;
}

C++ 解法, 执行用时: 19ms, 内存消耗: 2360KB, 提交时间: 2022-05-31

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    
    void backtracking(int n,int k, int startIndex,vector<vector<int>>& result,vector<int>& path)
    {
        if(path.size()==k)
        { 
            result.emplace_back(path);
            return;
        }
        for(int i=startIndex;i<=n-k+path.size()+1;i++)
        {
            path.push_back(i);
            backtracking(n,k,i+1,result,path);
            path.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> result; 
        vector<int> path; 
        backtracking(n,k,1,result,path);
        return result;
    }
};

详情