C# Program to Find All Subsets of a Set

You can find all subsets of a set in C# by using recursion with a method that adds each element either included or excluded, like FindSubsets(int[] set, int index, List current, List> result).

Examples

Input[1]

Output[[], [1]]

Input[1, 2]

Output[[], [1], [2], [1, 2]]

Input[]

Output[[]]

How to Think About It

To find all subsets, think of each element as having two choices: either it is in the subset or it is not. Start with an empty subset and move through the set elements one by one, branching into two paths at each element: one including it and one excluding it. Collect all these subsets as you go.

Algorithm

1

Start with an empty list to hold all subsets.

2

Define a recursive function that takes the current index and the current subset.

3

If the index reaches the end of the set, add the current subset to the list of all subsets.

4

Otherwise, call the function twice: once excluding the current element, once including it.

5

Return the list of all subsets after recursion completes.

Code

csharp

using System;
using System.Collections.Generic;

class Program {
    static void FindSubsets(int[] set, int index, List<int> current, List<List<int>> result) {
        if (index == set.Length) {
            result.Add(new List<int>(current));
            return;
        }
        // Exclude current element
        FindSubsets(set, index + 1, current, result);
        // Include current element
        current.Add(set[index]);
        FindSubsets(set, index + 1, current, result);
        current.RemoveAt(current.Count - 1);
    }

    static void Main() {
        int[] set = {1, 2, 3};
        var result = new List<List<int>>();
        FindSubsets(set, 0, new List<int>(), result);
        foreach (var subset in result) {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

Output

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

Dry Run

Let's trace the input [1, 2] through the code

1

Start recursion at index 0

Current subset: []

2

Exclude element 1 at index 0

Current subset: []

3

Exclude element 2 at index 1

Current subset: [] -> Add [] to result

4

Include element 2 at index 1

Current subset: [2] -> Add [2] to result

5

Include element 1 at index 0

Current subset: [1]

6

Exclude element 2 at index 1

Current subset: [1] -> Add [1] to result

7

Include element 2 at index 1

Current subset: [1, 2] -> Add [1, 2] to result

Index	Current Subset	Action	Result List
0	[]	Exclude 1	[]
1	[]	Exclude 2	[[]]
1	[]	Include 2	[[], [2]]
0	[]	Include 1	[[], [2]]
1	[1]	Exclude 2	[[], [2], [1]]
1	[1]	Include 2	[[], [2], [1], [1, 2]]

Why This Works

Step 1: Recursive branching

The code uses recursion to explore two paths at each element: including it or excluding it, which covers all subset possibilities.

Step 2: Base case

When the index reaches the length of the set, the current subset is complete and added to the result list.

Step 3: Backtracking

After including an element and recursing, the element is removed to restore the state for the next recursive call excluding it.

Alternative Approaches

Iterative bit manipulation

csharp

using System;
using System.Collections.Generic;

class Program {
    static List<List<int>> FindSubsetsIterative(int[] set) {
        var result = new List<List<int>>();
        int n = set.Length;
        int total = 1 << n; // 2^n subsets
        for (int i = 0; i < total; i++) {
            var subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subset.Add(set[j]);
                }
            }
            result.Add(subset);
        }
        return result;
    }

    static void Main() {
        int[] set = {1, 2, 3};
        var subsets = FindSubsetsIterative(set);
        foreach (var subset in subsets) {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

This method uses bitwise operations to generate subsets iteratively, which can be faster but less intuitive than recursion.

Using LINQ Aggregate

csharp

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main() {
        int[] set = {1, 2, 3};
        var subsets = set.Aggregate(
            new List<List<int>> { new List<int>() },
            (acc, val) => acc.Concat(acc.Select(x => x.Concat(new[] { val }).ToList())).ToList()
        );
        foreach (var subset in subsets) {
            Console.WriteLine("[" + string.Join(", ", subset) + "]");
        }
    }
}

This approach uses LINQ to build subsets by adding each element to existing subsets, which is concise but may be less clear for beginners.

Complexity: O(2^n * n) time, O(2^n * n) space

Time Complexity

There are 2^n subsets for a set of size n, and each subset can take up to O(n) time to copy or print, so total time is O(2^n * n).

Space Complexity

We store all subsets, which can be up to 2^n subsets each of size up to n, so space is O(2^n * n).

Which Approach is Fastest?

The iterative bit manipulation approach is generally faster due to less overhead, but recursion is easier to understand and implement.

Approach	Time	Space	Best For
Recursive Backtracking	O(2^n * n)	O(2^n * n)	Clarity and teaching recursion
Iterative Bit Manipulation	O(2^n * n)	O(2^n * n)	Performance and bitwise operations
LINQ Aggregate	O(2^n * n)	O(2^n * n)	Concise code using functional style