注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex216 Combination Sum III  

2015-05-24 21:19:31|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.


Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]


Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

限制了递归深度,比ex39 和ex40还简单一些。也就是说递归3次,如果不等的话就结束了。如下代码

class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> combinationSum3(int k, int n) {
if (k <= 0)
return result;
//这里的递归深度必须是k
int nums = 9;
vector<int> candidates;
int i, j;
for (i = 1; i <= nums; i++)
{
candidates.push_back(i);
}
int sum = 0;
int depth = 0;
vector<int>tmp;
traverse(candidates,n,sum,0,tmp,k,0);
return result;
}
void traverse(vector<int> candidates, int target, int sum, int depth, vector<int>index, int maxDepth, int n)
{
if (depth == maxDepth)
{
//退出条件
if (sum == target)
{
result.push_back(index);
}
return;
}
else
{
int len = candidates.size();
int i;
for (i = n; i < len; i++)
{
vector<int> temp = index;
temp.push_back(candidates[i]);
traverse(candidates, target, sum + candidates[i], depth + 1, temp, maxDepth, i + 1);
}
}
}
};



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017