# Three ways to do this(C#)

1. Clone the lists when process each num.

At beginning, there is only one empty list.

{{}}

When we process the first num( use 1 to represent), clone all the existing list, for the cloned list, add the cur num to the list. . Add all the cloned list to the result.

{{},{1}}

when we process the second num( use 2 to represent), again clone all existing list, and add cur num to the cloned list. Add all the cloned list to the result.

{{},{1},{2},{1,2}}

do this until n.

``````public IList<IList<int>> Subsets(int[] nums)
{
Array.Sort(nums);
IList<IList<int>> res = new List<IList<int>>();
if( nums == null || nums.Length == 0 ) return res;

for( int i = 0; i < nums.Length; ++i )
{
int count = res.Count;
for( int j = 0; j < count; ++j )
{
List<int> newList = new List<int>( res[j] );
}

}
return res;
}
``````

## 2.Bit manipulation

go from 0 to Pow(2, nums.Length)

0 -> 0000 -> {}

1 -> 0001 -> {1} // {1} means the list contains the first num in the array nums

2 -> 0010 -> {2}

3 -> 0011 -> {2,1}

.....

Pow(2, nums.Length) -> ......

Add all above list to the result.

``````public IList<IList<int>> Subsets(int[] nums)
{
Array.Sort(nums);

IList<IList<int>> result = new List<IList<int>>();

int max =  (int)Math.Pow(2, nums.Length);
for( int counter = 0; counter < max; ++counter )
{
IList<int> subSet = new List<int>();
int mark = 1;
for( int j = 0; j < nums.Length; ++j )
{
if( (mark & counter) != 0 )
{
}
mark <<= 1;
}

}

return result;

}
``````
1. Back tracking

When process each num, there're two choice, add or do not add. If add, a back track is needed.

``````public class Solution {
public IList<IList<int>> Subsets(int[] nums)
{
Array.Sort(nums);

IList<IList<int>> res = new List<IList<int>>();
IList<int> list = new List<int>();

Subset(res, list, nums, 0);

return res;
}

private void Subset( IList<IList<int>> res, IList<int> list, int[] nums, int index )
{
if( index == nums.Length )
{
return;
}

int count = list.Count;
Subset( res, list, nums,index +1 );