leetcode 组合总和深搜

野性酷女 2023-08-17 15:43 42阅读 0赞

> 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

> 说明：

> 所有数字都是正整数。  
> 解集不能包含重复的组合。  
> 示例 1:

> 输入: k = 3, n = 7  
> 输出: \[\[1,2,4\]\]  
> 示例 2:

> 输入: k = 3, n = 9  
> 输出: \[\[1,2,6\], \[1,3,5\], \[2,3,4\]\]

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/combination-sum-iii][https_leetcode-cn.com_problems_combination-sum-iii]

思路：分析DFS，需要的参数必然有数的个数，数的总和，在函数内部枚举第一个数，然后去递归枚举第二个数直到k个数，若满足条件就加入答案，由于不能有重复，所以枚举的时候确定一个顺序，顺序枚举就行，这样会避免1+2+4和4+1+2都出现，所以传参数还需要有一个枚举起点。

class Solution {
    public:
        vector<vector<int>> ans;
        vector<int> path;
        vector<vector<int>> combinationSum3(int k, int n) {
            dfs(k,n,1);
            return ans;
        }
        void dfs(int k,int n,int start)
        {
            if(!k){
                if(!n)ans.push_back(path);
                return;
            }
    //k个数，需要剩下的数有K个数，9-i+1>=k,则i<=10-k
            for(int i=start;i<=10-k;++i){
                if(n>=i){//只有n>=i的时候才能加进去
                    path.push_back(i);
                    dfs(k-1,n-i,i+1);
                    path.pop_back();
                }
            }
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11363291.html

[https_leetcode-cn.com_problems_combination-sum-iii]: https://leetcode-cn.com/problems/combination-sum-iii

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - 39 组合总和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [39. 组合总和 - 力扣（LeetCod

￡神魔★判官ぃ/ 2023年09月26日 11:25/ 0 赞/ 57 阅读

相关 leetcode 组合总和深搜

> 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 > 说明： > 所有数字都是正整数。 > 解集

野性酷女/ 2023年08月17日 15:43/ 0 赞/ 43 阅读

相关【LeetCode 39】组合总和

题目描述给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 can

深碍√TFBOYSˉ_/ 2022年12月05日 05:15/ 0 赞/ 161 阅读

相关 LeetCode 39. 组合总和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

痛定思痛。/ 2022年11月01日 15:58/ 0 赞/ 188 阅读

相关 leetcode 39 组合总和

前言题目：[39. 组合总和][39.] 参考题解：[组合总和-代码随想录][-] -------------------- 提交代码画出树状图，代码思路

我会带着你远行/ 2022年09月12日 11:51/ 0 赞/ 185 阅读

相关 Leetcode 39. 组合总和

题目重述给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一

旧城等待，/ 2022年09月09日 04:36/ 0 赞/ 213 阅读

相关 LeetCode 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例: nums = [1, 2, 3] target = 4

ゞ浴缸里的玫瑰/ 2022年04月08日 09:47/ 0 赞/ 230 阅读

相关【leetcode】组合总和 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2022年03月11日 10:10/ 0 赞/ 238 阅读

相关 leetcode:39.组合总和

题目描述：给定一个无重复元素的数组 `candidates`和一个目标数 `target`，找出 `candidates`中所有可以使数字和为 `target`的组合。

朱雀/ 2022年02月16日 04:53/ 0 赞/ 237 阅读

相关 LeetCode-39.组合总和

题目给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candi

╰+哭是因爲堅強的太久メ/ 2022年01月27日 15:37/ 0 赞/ 255 阅读