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

HT·生活

123

 
 
 

日志

 
 

ex40 Combination Sum II  

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

  下载LOFTER 我的照片书  |

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

Each number in C may only be used once in the combination.

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 10,1,2,7,6,1,5 and target 8
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 


和39题几乎一样,就是每个元素只能用一次,而且可能有重复的元素。所以就开了一个sign数组来进行标记,当前元素是否用过了,而且如果遇到了和上一个一样的元素,如果上一个没用的话,这一个也不能用。这是一个限制条件,保证最后不会出现重复的结果。见代码

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

sort(candidates.begin(), candidates.end());
vector<bool>tmp(candidates.size(),false);
sign = tmp;
//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]);
//开一个数组sign标记,如果前面一个和当前的相等,并且前面的那个sign是true
//也就是前面的用过了,这个才能用
//也可以再用过这个后,把和这个相等的元素都跳过去
if (i > 0 && candidates[i] == candidates[i - 1] && sign[i-1] == false)
continue;
sign[i] = true;
traverse(candidates, target, sum + candidates[i], depth + 1, temp, maxDepth, i+1);
sign[i] = false;
}
}
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;
}
}
};


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

历史上的今天

评论

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

页脚

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