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
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
Printing All Subsets Of A Given Set Or The Power Set Problem
Step 2
Printing All Subsets Of A Given Set Or The Power Set Problem
Step 3
Printing All Subsets Of A Given Set Or The Power Set Problem
Step 4
Printing All Subsets Of A Given Set Or The Power Set Problem
 
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,
  1. using System.IO;  
  2. using System.Collections.Generic;  
  3. using System;  
  4.   
  5. class Program  
  6. {  
  7.     static void Main()  
  8.     {  
  9.         //Setting Up the Array   
  10.         int[] arr = {1,3,2};  
  11.           
  12.         //Calling the Mediator Function vis passing the array  
  13.         FindSubsets(arr);  
  14.           
  15.         Console.WriteLine("----End----");  
  16.          
  17.     }  
  18.       
  19.     static void FindSubsets(int[] arr){  
  20.         int[] sub = new int[arr.Length];  
  21.         Find(arr,sub,0);  
  22.     }  
  23.       
  24.     static void Find(int[] arr,int[] sub,int p){  
  25.         //if the position variable p has iterated all elements   
  26.         if(p==arr.Length){  
  27.             //mechanism to print non zero elements  
  28.             string s = "";  
  29.             for(int i=0;i<arr.Length;i++){  
  30.                 if(sub[i]!=0){  
  31.                     s += sub[i].ToString();  
  32.                 }  
  33.             }  
  34.             Console.WriteLine(s);  
  35.         }  
  36.         else{  
  37.             //For not selecting the element  
  38.             sub[p] = 0;  
  39.             Find(arr,sub,p+1);  
  40.               
  41.             //For selecting the element  
  42.             sub[p] = arr[p];  
  43.             Find(arr,sub,p+1);  
  44.               
  45.         }  
  46.     }  
  47. }  
Output
Printing All Subsets Of A Given Set Or The Power Set Problem
References
 
https://www.geeksforgeeks.org/backtracking-introduction/#:~:text=Backtracking%20can%20be%20defined%20as,search%20for%20a%20feasible%20solution.
 
P.S: If you have a better approach don't forget to link it in the comment section below. Happy Coding!