Problem

Given a set of distinct integers, 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,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InterviewPrepQuestions.Backtracking
{
    class Subsets
    {
        public IList<IList<int>> SubsetsWithDup(int[] nums)
        {
            IList<IList<int>> result = new List<IList<int>>();
            Array.Sort(nums);
            Backtrack(result, new List<int>(), nums, 0);
            return result;
        }

        private void Backtrack(IList<IList<int>> result, List<int> tempList, int[] nums, int start)
        {
            result.Add(new List<int>(tempList));
            for(int i = start; i < nums.Length; i++)
            {
                if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicates
                tempList.Add(nums[i]);
                Backtrack(result, temp List, nums, i + 1);
                tempList.RemoveAt(tempList.Count - 1);
            }
        }
    }
}