Recursive program to generate power set using Recursion

Recursive program to generate power set using Backtracking:

Recursive program to generate power set using Backtracking using Bottom Up Approach:

The idea is to consider two cases for every character.
(i) Consider current character as part of current subset
(ii) Do not consider current character as part of the current subset.

Follow the approach to implement the above idea:

The base condition of the recursive approach is when the current index reaches the size of the given string (i.e, index == n). then print the current string say, curr.
Make two recursive calls for the two cases for every character
- We consider the character as part of the current subset
- We do not consider current character as part of the current subset

Follow the steps below to implement the above approach:

C++

// CPP program to generate power set 
#include <bits/stdc++.h> 
using namespace std; 
  
// str : Stores input string 
// curr : Stores current subset 
// index : Index in current subset, curr 
void powerSet(string str, int index = 0, string curr = "") 
{ 
    int n = str.length(); 
  
    // base case 
    if (index == n) { 
        cout << curr << endl; 
        return; 
    } 
  
    // Two cases for every character 
    // (i) We consider the character 
    // as part of current subset 
    // (ii) We do not consider current 
    // character as part of current 
    // subset 
    powerSet(str, index + 1, curr + str[index]); 
    powerSet(str, index + 1, curr); 
} 
  
// Driver code 
int main() 
{ 
    string str = "abc"; 
    powerSet(str); 
    return 0; 
}

Java

// Java program to generate power set 
class GFG { 
  
    // str : Stores input string 
    // curr : Stores current subset 
    // index : Index in current subset, curr 
    static void powerSet(String str, int index, String curr) 
  
    { 
        int n = str.length(); 
  
        // base case 
        if (index == n) { 
            System.out.println(curr); 
            return; 
        } 
  
        // Two cases for every character 
        // (i) We consider the character 
        // as part of current subset 
        // (ii) We do not consider current 
        // character as part of current 
        // subset 
        powerSet(str, index + 1, curr + str.charAt(index)); 
        powerSet(str, index + 1, curr); 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        String str = "abc"; 
        int index = 0; 
        String curr = ""; 
        powerSet(str, index, curr); 
    } 
} 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to generate power set 
def powerSet(string, index, curr): 
  
    # string : Stores input string 
    # curr : Stores current subset 
    # index : Index in current subset, curr 
    if index == len(string): 
        print(curr) 
        return
  
    powerSet(string, index + 1, 
             curr + string[index]) 
    powerSet(string, index + 1, curr) 
  
  
# Driver Code 
if __name__ == "__main__": 
  
    s1 = "abc"
    index = 0
    curr = "" 
    powerSet(s1, index, curr) 
  
# This code is contributed by Ekta Singh 

C#

// C# program to generate power set 
using System; 
  
class GFG { 
  
    // str : Stores input string 
    // curr : Stores current subset 
    // index : Index in current subset, curr 
    static void powerSet(String str, int index, String curr) 
  
    { 
        int n = str.Length; 
  
        // base case 
        if (index == n) { 
            Console.WriteLine(curr); 
            return; 
        } 
  
        // Two cases for every character 
        // (i) We consider the character 
        // as part of current subset 
        // (ii) We do not consider current 
        // character as part of current 
        // subset 
        powerSet(str, index + 1, curr + str[index]); 
        powerSet(str, index + 1, curr); 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        String str = "abc"; 
        int index = 0; 
        String curr = ""; 
        powerSet(str, index, curr); 
    } 
} 
  
// This code is contributed by Rajput-Ji

Javascript

<script> 
// Javascript program to generate power set 
      
    // str : Stores input string 
// curr : Stores current subset 
// index : Index in current subset, curr 
    function powerSet(str,index,curr) 
    { 
        let n = str.length; 
   
    // base case 
    if (index == n) 
    { 
        document.write(curr+"<br>"); 
        return; 
    } 
   
    // Two cases for every character 
    // (i) We consider the character 
    // as part of current subset 
    // (ii) We do not consider current 
    // character as part of current 
    // subset 
    powerSet(str, index + 1, curr + str[index]); 
    powerSet(str, index + 1, curr); 
    } 
      
    // Driver code 
    let str = "abc"; 
    let index = 0; 
    let curr=""; 
    powerSet(str,index,curr); 
      
      
// This code is contributed by avanitrachhadiya2155 
</script>

Output

abc
ab
ac
a
bc
b
c

Time Complexity: O(2ⁿ)
Auxiliary Space: O(n), For recursive call stack

Recursive program to generate power set

Given a set represented as a string, write a recursive code to print all subsets of it. The subsets can be printed in any order.

Examples:

Input : set = “abc”
Output : { “”, “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”}

Input : set = “abcd”
Output : { “”, “a” ,”ab” ,”abc” ,”abcd”, “abd” ,”ac” ,”acd”, “ad” ,”b”, “bc” ,”bcd” ,”bd” ,”c” ,”cd” ,”d” }

Tags:

#DSA #Mathematical #Mathematical