Printing All Subsets Of A Given Set Or The Power Set Problem

The aim is simply to print all the possible subsets of a given set. There is not a naive simple loop approach that I could come up with to solve this problem, so we will tackle it here using the second easiest methodology, which is the Recursive Approach.

We would use a technique called backtracking in which we will check out every possible path for our required outcome. I'm attaching in the references a link to backtracking blog, if you want to dive into more detail.

Problem Statement

Given,

Set A = {1,2,3}

Output

1

2

3 

1,2

1,3

2,3

1,2,3

Note

The Order is not relevant for this solution.

Now, how do we approach this problem?

The simplest way to think about this problem is that we have to iterate all the elements and for each element, we have to decide whether to include it in our current set or not.

Follow the images below to understand better:

Step 1

Step 2

Step 3

Step 4

Now how to implement this knowledge into coding?

Here’s my approach.

Forget everything and just focus on the fact that the only useful information in this problem is the set itself.

Step 1

Set up the array

Step 2

Start the program

Step 3

Recursively call the function for each value to generate a sub-array

Now the trouble is what should our recursive function be doing?

When designing a recursive function the first thing is to understand our base condition or end condition, in this case when we have iterated through the whole loop that’s when our progression should stop. Clearly, this means that the main array and the element that we are iterating through have to be involved in the recursive function.

In my approach, I used p as a position variable to keep track of which element is being checked.

When position variable p is equal to the length of the array, the execution stops.

Now for the iterative condition, we have 2 choices

1. Do not select the element

2. Select the element

When the element is not selected I have assigned it a value 0, on the contrary, when the element is selected I have added it into my sub-array.

Refer to code,

using System.IO;  
using System.Collections.Generic;  
using System;  
  
class Program  
{  
    static void Main()  
    {  
        //Setting Up the Array   
        int[] arr = {1,3,2};  
          
        //Calling the Mediator Function vis passing the array  
        FindSubsets(arr);  
          
        Console.WriteLine("----End----");  
         
    }  
      
    static void FindSubsets(int[] arr){  
        int[] sub = new int[arr.Length];  
        Find(arr,sub,0);  
    }  
      
    static void Find(int[] arr,int[] sub,int p){  
        //if the position variable p has iterated all elements   
        if(p==arr.Length){  
            //mechanism to print non zero elements  
            string s = "";  
            for(int i=0;i<arr.Length;i++){  
                if(sub[i]!=0){  
                    s += sub[i].ToString();  
                }  
            }  
            Console.WriteLine(s);  
        }  
        else{  
            //For not selecting the element  
            sub[p] = 0;  
            Find(arr,sub,p+1);  
              
            //For selecting the element  
            sub[p] = arr[p];  
            Find(arr,sub,p+1);  
              
        }  
    }  
}

Output

References

https://www.geeksforgeeks.org/

P.S: If you have a better approach don't forget to link it in the comment section below. Happy Coding!