Find Subsets of a Given Array

In this article, we'll find all subsets of an array in C#. We will use a bit manipulation trick where each subset corresponds to a binary representation of an integer.

using System;
using System.Collections.Generic;
public class Program
{
    public static void Main()
    {
        int[] arr = { 1, 2, 3 };
        var subsets = GetSubsets(arr);
        foreach (var subset in subsets)
        {
            Console.WriteLine(string.Join(", ", subset));
        }
    }
    public static List<List<int>> GetSubsets(int[] arr)
    {
        List<List<int>> subsets = new List<List<int>>();
        int count = (int)Math.Pow(2, arr.Length);
        for (int i = 0; i < count; i++)
        {
            List<int> subset = new List<int>();
            for (int j = 0; j < arr.Length; j++)
            {
                if ((i & (1 << j)) != 0)
                {
                    subset.Add(arr[j]);
                }
            }
            subsets.Add(subset);
        }
        return subsets;
    }
}

In this code, the GetSubsets function generates all subsets of the given array. It does this by iterating from 0 to 2^n - 1 (where n is the length of the array), treating the binary representation of the current number as a mask for whether to include each element in the current subset (1 means include, 0 means exclude). Each subset is then added to the list of all subsets. The Main function then prints out each subset.

Here’s a breakdown of how the GetSubsets method works.

1. List<List<int>> subsets = new List<List<int>>();: This line initializes a list to hold all the subsets.
2. int count = (int)Math.Pow(2, arr. Length);: This line calculates the total number of possible subsets, which is 2^n where n is the number of elements in the array.
3. for (int i = 0; i < count; i++): This outer loop iterates over all numbers from 0 to 2^n - 1. Each number i in this range represents a unique subset of the array.
4. List<int> subset = new List<int>();: This line initializes a list to hold the current subset.
5. for (int j = 0; j < arr.Length; j++): This inner loop iterates over each element in the array.
6. if ((i & (1 << j)) != 0): This line checks whether the j-th bit of i is set. If it is, that means the j-th element of the array should be included in the current subset.
7. subset.Add(arr[j]);: If the jth bit of i is set, this line adds the j-th element of the array to the current subset.
8. subsets.Add(subset);: After all elements have been checked, this line adds the current subset to the list of all subsets.
9. return subsets: Finally, the method returns the list of all subsets.

Summary

The above GetSubsets method generates all possible subsets of the input array by treating each number from 0 to 2^n - 1 as a binary mask that indicates which elements to include in each subset.

The time complexity of the above code is O(n * 2^n).

Let's take one example.

Suppose {1,2,3} is the input array, then no. of subsets will be 2^n, which is 2^3, and the outer loop will run 8 times, and for every i it will do bit & operation by left shift 1 by j.

The loop will run 2^3 times.

1. i = 0 (000 in binary): Subset is {}.
2. i = 1 (001 in binary): i & (1 << 0) is 1. Subset is {1}.
3. i = 2 (010 in binary): i & (1 << 1) is 2. Subset is {2}.
4. i = 3 (011 in binary): i & (1 << 0) and i & (1 << 1) are 1 and 2. Subset is {1, 2}.
5. i = 4 (100 in binary): i & (1 << 2) is 3. Subset is {3}.
6. i = 5 (101 in binary): i & (1 << 0) and i & (1 << 2) are 1 and 3. Subset is {1, 3}.
7. i = 6 (110 in binary): i & (1 << 1) and i & (1 << 2) are 2 and 3. Subset is {2, 3}.
8. i = 7 (111 in binary): i & (1 << 0), i & (1 << 1), and i & (1 << 2) are 1, 2, and 3. Subset is {1, 2, 3}.

So, the output of the function for the array {1, 2, 3} would be a list of all these subsets: {}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}.