LeetCode 39题:组合总和

这篇具有很好参考价值的文章主要介绍了LeetCode 39题:组合总和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目

代码

官方提供


题目

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int len=0;
int size=0;
int*columnsize;

int search(int target,int**res,int*combine,int ind,int*candidates,int candidatesSize);
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes);

int main()
{
    int candidates[4] = {2,3,5}, target = 8;
    int *returnSizes=(int*)malloc(sizeof(int)),**returnColumnSize=(int**)malloc(sizeof(int*));
    returnColumnSize[0]=(int*)malloc(sizeof(int));
    int **res=combinationSum(candidates,3,target,returnSizes,returnColumnSize);
    for(int i=0;i<*returnSizes;i++)
    {
        for(int j=0;j<returnColumnSize[0][i];j++)
        {
            printf("%d ",res[i][j]);
        }
        printf("\n");
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
{
    columnsize=(int*)malloc(sizeof(int));
    int**res=(int**)malloc(sizeof(int*)*150);
    if(candidates[0]>target)
    {
        *returnSize=0;
        returnColumnSizes[0][*returnSize]=0;
        return NULL;
    }
    int*combine=(int*)malloc(sizeof(int)*(target/candidates[0]+1)); 
    int t= search(target,res,combine,0,candidates,candidatesSize);
    *returnSize=size;
    returnColumnSizes[0]=columnsize;
    return res;
}

int search(int target,int**res,int*combine,int ind,int*candidates,int candidatesSize)
{
    if(target<0)
    {
        return 1;
    }
    if(target==0)
    {
        size++;
        columnsize=(int*)realloc(columnsize,sizeof(int)*size);
        columnsize[size-1]=len;
        int *temp=(int *)malloc(sizeof(int)*len);
        for(int i=0;i<len;i++)
        {
            temp[i]=combine[i];
        }
        res[size-1]=temp;
        return 1;
    }
    else 
    {
        for(int i=ind;i<candidatesSize;i++)
        {
            combine[len++]=candidates[i];        
            int t=len;
            int sign=search(target-candidates[i],res,combine,i,candidates,candidatesSize);
            len--;
            if(sign==1)
            {
                break;
            }
        }
    }
    return 0;
}

官方提供

尝试用「搜索回溯」的方法来解决。当然,搜索回溯的过程一定存在一些优秀的剪枝方法来使得程序运行得更快,而这里只给出了最朴素不含剪枝的写法

int candidatesSize_tmp;

int ansSize;

int combineSize;

int* ansColumnSize;

void dfs(int* candidates, int target, int** ans, int* combine, int idx) {
    if (idx == candidatesSize_tmp) {
        return;
    }
    if (target == 0) {
        int* tmp = malloc(sizeof(int) * combineSize);
        for (int i = 0; i < combineSize; ++i) {
            tmp[i] = combine[i];
        }
        ans[ansSize] = tmp;
        ansColumnSize[ansSize++] = combineSize;
        return;
    }
    // 直接跳过
    dfs(candidates, target, ans, combine, idx + 1);
    // 选择当前数
    if (target - candidates[idx] >= 0) {
        combine[combineSize++] = candidates[idx];
        dfs(candidates, target - candidates[idx], ans, combine, idx);
        combineSize--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    candidatesSize_tmp = candidatesSize;
    ansSize = combineSize = 0;
    int** ans = malloc(sizeof(int*) * 1001);
    ansColumnSize = malloc(sizeof(int) * 1001);
    int combine[2001];
    dfs(candidates, target, ans, combine, 0);
    *returnSize = ansSize;
    *returnColumnSizes = ansColumnSize;
    return ans;
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/combination-sum/solutions/406516/zu-he-zong-he-by-leetcode-solution/
来源:力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-654681.html

 

 

到了这里,关于LeetCode 39题:组合总和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 39. 组合总和(回溯+剪枝)

    链接:LeetCode 39. 组合总和 难度:中等 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选

    2024年02月14日
    浏览(43)
  • LeetCode(力扣)39. 组合总和Python

    https://leetcode.cn/problems/combination-sum/description/

    2024年02月09日
    浏览(35)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(50)
  • leetcode216. 组合总和 III(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输

    2024年02月10日
    浏览(45)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(42)
  • 【Leetcode】377. 组合总和 Ⅳ

    题目链接🔗 给你一个由 不同 整数组成的数组 n u m s nums n u m s ,和一个目标整数 t a r g e t target t a r g e t 。请你从 n u m s nums n u m s 中找出并返回总和为 t a r g e t target t a r g e t 的元素组合的个数。 题目数据保证答案符合 32 32 32 位整数范围。 示例 1: **输入:**nums = [1,2,3],

    2024年04月23日
    浏览(38)
  • LeetCode-216-组合总和Ⅱ

    题目链接: LeetCode-216-组合总和Ⅱ 解题思路:回溯算法 注意事项注释中有 代码实现:

    2024年02月09日
    浏览(43)
  • LeetCode 377. 组合总和 Ⅳ

    解题思路 之前一直以为这是背包问题,后来发现,这个是有顺序的, 而背包问题是无序的,但是我们也可以用dp分析法来分析。 相关代码

    2024年04月12日
    浏览(43)
  • 【LeetCode:216. 组合总和 III + 递归】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年04月25日
    浏览(52)
  • 40. 组合总和 II - 力扣(LeetCode)

    题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 输入示例 输出示例 解题代码

    2024年01月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包