题目描述：
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); } }
?
|