Subsets II

List every subset of numbers that may contain duplicates, without listing the same subset twice. Sort, then never start two branches with the same value at one depth.

The idea

Plain subsets backtracking builds a subset once per choice of positions, so [1, 2a] and [1, 2b] come out as two copies of [1, 2]. After sorting, equal values are neighbours. At one depth, the loop decides which value comes next; starting with the second 2 would only rebuild what starting with the first 2 already built. So skip nums[i] when it equals nums[i - 1] and i > start. Going deeper is still allowed, which is how [2, 2] gets built.

Code

public IList<IList<int>> SubsetsWithDup(int[] nums) {
    Array.Sort(nums); // equal values now sit side by side
    var result = new List<IList<int>>();
    Backtrack(nums, 0, new List<int>(), result);
    return result;
}

void Backtrack(int[] nums, int start, List<int> path, List<IList<int>> result) {
    result.Add(new List<int>(path)); // every path is a subset
    for (int i = start; i < nums.Length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // same value already tried at this depth
        path.Add(nums[i]);
        Backtrack(nums, i + 1, path, result);
        path.RemoveAt(path.Count - 1);
    }
}

Tips

• The condition is i > start, not i > 0: the first copy at each depth must be allowed, otherwise [2, 2] would never appear.
• Without sorting, equal values are not neighbours and the skip check misses them.
• In the recursion tree, every dashed red "dup" node is a whole branch that would only have repeated an earlier one.

In the .NET library

new List<int>(path) stores a copy. Adding path itself would store one shared list that ends up empty after all the RemoveAt calls.