湖州城市投资建设集团网站,wordpress定制网页,龙华区是深圳最差的区,河南智慧团建网站登录1. 题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数#xff0c;并且每种组合中不存在重复的数字。
说明#xff1a;
所有数字都是正整数。
解集不能包含重复的组合。 示例 1:
输入: k 3, n 7
输出: [[1,2,4]]示例 2:
输入: k 3, n 9
输出…1. 题目
找出所有相加之和为 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 相关题目LeetCode 39. 组合总和排列组合 回溯
2. 回溯解题
关键在于如何避免重复每次取了一个数 i 那么下次取得数只能比 i 大这样避免重复组合
class Solution {
public:vectorvectorint combinationSum3(int k, int n) {vectorvectorint ans;vectorint cb;bt(0,0,k,0,n,cb,ans);return ans;}void bt(int num, int count, int k, int sum, int n, vectorint cb, vectorvectorint ans) {if(sum n || 9-num k-count)//和超了或者剩余的数不够个数return;if(count k){if(sum n)ans.push_back(cb);return;}for(int j num1; j 9; j)//每次取num1避免重复{cb.push_back(j);bt(j,count1,k,sumj,n,cb,ans);cb.pop_back();}}
};0 ms 6.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
