频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
LeetCode -- Subsets II
2015-11-18 16:11:00         来源:Stay focus,Stay Crazy  
收藏   我要投稿
题目描述:


Given a collection of integers that might contain duplicates, nums, return all possible subsets.


Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:


[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


思路:
又是一道backtracking题目。
本题与Combination Sum极为类似。


需要注意去重,使用哈希来存升序key。


实现代码:

public class Solution {
    public IList> SubsetsWithDup(int[] nums) 
    {
    	Dictionary> result = new Dictionary>();
    	Travel(nums.ToList() ,new List(), 0, result);
    	
    	return result.Values.ToList();
    }


private void Travel(IList nums, IList arr, int index, Dictionary> result)
{
	var k = K(ref arr);
	if(!result.ContainsKey(k)){
		result.Add(k, new List(arr));
	}
	
	for(var i = index ;i < nums.Count; i++){
		arr.Add(nums[i]);
		Travel(nums, arr, i + 1, result);
		arr.Remove(nums[i]);
	}
}


private string K(ref IList arr){
	arr = arr.OrderBy(x=>x).ToList();
	return string.Join(,, arr);
}


}
 
点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:POI操作Excel设置前景色背景色
下一篇:LeetCode -- Single Number III
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站