LeetCode -- Subsets II

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。


實現代碼：

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);
}


}