C# counting sort and then work on same integer together
It is my first practice in 2019. I choose to sort the number in the array and then save into SortedDictionary using counting sort, and then work on each integer in ascending order one by one.
Case study [1, 2, 2]
Counting sort, so there is one for number 1, two for number 2.
Work on each integer in ascending order one by one. First one is empty set, and then work on number 1, each set is appended by number 1, and then next number 2, we work together those two numbers with the same value 2.
Work on each integer in ascending order one by one. First one is empty set, and then work on number 1, each set is appended by number 1, and then next number 2, we work together those two numbers with the same value 2.
The are three cases for two numbers with the same value 2. 0 copy, 1 copy, or two copies, three options.
So the answer will be
[]
[1],
[] appended by 2 zero time, 1 time, two times, [], [2], [2,2]
[1] appended by 2 zero time, 1 time, two times, [1],[1,2], [1, 2,2]
[]
[1],
[] appended by 2 zero time, 1 time, two times, [], [2], [2,2]
[1] appended by 2 zero time, 1 time, two times, [1],[1,2], [1, 2,2]
The way we handle the numbers in the above, the duplicate numbers will not be created.
Here are highlights:
public class Solution {
/// <summary>
/// June 22, 2019
/// The idea is to sort the numbers using counting sort and
/// save it in SorteDictionary<int, int>.
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public IList<IList<int>> SubsetsWithDup(int[] numbers)
{
if (numbers == null || numbers.Length == 0)
return null;
var sorted = new SortedDictionary<int, int>();
var length = numbers.Length;
for(int i = 0; i < length; i++)
{
var current = numbers[i];
if (!sorted.ContainsKey(current))
sorted.Add(current, 0);
sorted[current]++;
}
var result = new List<IList<int>>();
// empty set - base case
var sublist = new List<int>();
var list = new List<IList<int>>();
//list.Add(sublist); // caught by debugger
foreach(var key in sorted.Keys)
{
var value = sorted[key];
var nextList = new List<IList<int>>();
// edge case
if (list.Count == 0)
{
var nextSubList1 = new List<int>();
nextList.Add(nextSubList1);
for (int i = 0; i < value; i++)
{
var nextSubList = new List<int>();
for (int j = 0; j <= i; j++)
{
nextSubList.Add(key);
}
nextList.Add(nextSubList);
}
}
else
{
foreach (var subList in list)
{
var nextSubList1 = new List<int>(subList);
nextList.Add(nextSubList1);
for (int i = 0; i < value; i++)
{
var nextSubList = new List<int>(subList);
for (int j = 0; j <= i; j++)
{
nextSubList.Add(key);
}
nextList.Add(nextSubList);
}
}
}
// move to next unique number
list = new List<IList<int>>();
foreach (var subList in nextList)
{
var copySubList = new List<int>(subList);
list.Add(copySubList);
}
}
return list;
}
}