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

HT·生活

123

 
 
 

日志

 
 

ex39 Combination Sum  

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

  下载LOFTER 我的照片书  |

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7
A solution set is: 
[7] 
[2, 2, 3] 

就是在给定集合里面找到子集的和等于target,每个元素都可以多次使用,需要考虑时候最后出现重复的结果,所以开始的时候先排序,然后去除重复的元素。最后再深度递归。貌似算法好慢的,可是我搜了一下网上的答案,貌似别人也是这么写的,我把排序去掉了还是这种情况。

class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int len = candidates.size();
if (len <= 0)
return result;

sort(candidates.begin(), candidates.end());
preProcess(candidates); //去除重复元素
vector<int> index;
traverse(candidates,target,0,0,index,1000,0);
return result;
}
void traverse(vector<int> candidates, int target,int sum,int depth,vector<int>index,int maxDepth,int n)
{
//n表示的是当前遍历的起点
//对于 2 3 6 7
//如果当前遍历的是3 那么下次也是从3开始 为了防止重复 不能跑到2上面去
//深度遍历的算法好像太慢了
if (sum > target)
{
return;//不用搜索了,因为已经太大了
}
if (sum == target)
{
vector<int>res;
res = index;
result.push_back(index);
return;
}
int i, len = candidates.size();
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);
}
}
void preProcess(vector<int>& candidates)
{
vector<int>::iterator ps = candidates.begin(),pe = ps;
while (ps < candidates.end())
{
while ((pe + 1) < candidates.end() && *(pe + 1) == *(ps))
{
candidates.erase(pe+1);
}

pe++;
ps = pe;
}
}
};


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

历史上的今天

评论

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

页脚

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