Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice

• Each element in a subset must be in non-descending order.
• The ordering between two subsets is free.
• The solution set must not contain duplicate subsets.

Have you met this question in a real interview?

Yes

Example

If S =[1,2,2], a solution is:

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

Challenge

Can you do it in both recursively and iteratively?

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        IList<IList<int>> results = new List<IList<int>>();

        if (nums == null){
            return results;
        }

        if (nums.Length == 0){
            results.Add(new List<int>());
            return results;
        }

        Array.Sort(nums);
        DFS(new List<int>(), nums, 0, results);
        return results;
    }
    // 递归三要素
    // 1. 递归的定义：在 Nums 中找到所有以 subset 开头的的集合，并放到 results
    private void DFS(List<int> subset, int[] nums, int offSet, IList<IList<int>> results)
    {
        // 2. 递归的拆解
        // deep copy
        // results.add(subset);
        results.Add(new List<int>(subset));

        for (int i = offSet; i < nums.Length; i++){
             if (i != offSet && nums[i]==nums[i-1]) {
                    continue;
                }
            // [1] -> [1,2]
            subset.Add(nums[i]);
            // 寻找所有以 [1,2] 开头的集合，并扔到 results
            DFS(subset, nums, i + 1, results);
            // [1,2] -> [1] 回溯
            subset.RemoveAt(subset.Count - 1);
        }
    }
}