LeetCode -- Subsets II
题目描述：
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。
实现代码：
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<IList<int>> SubsetsWithDup(int[] nums)
{
Dictionary<string, IList<int>> result = new Dictionary<string, IList<int>>();
Travel(nums.ToList() ,new List<int>(), 0, result);
return result.Values.ToList();
}
private void Travel(IList<int> nums, IList<int> arr, int index, Dictionary<string , IList<int>> result)
{
var k = K(ref arr);
if(!result.ContainsKey(k)){
result.Add(k, new List<int>(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<int> arr){
arr = arr.OrderBy(x=>x).ToList();
return string.Join(",", arr);
}
}