Recursive program to generate power set using Backtracking

Recursive program to generate power set using Recursion:

The idea is to fix a prefix, and generate all subsets beginning with the current prefix. After all subsets with a prefix are generated, replace the last character with one of the remaining characters.

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 return
First, print the current subset
Iterate over the given string from the current index (i.e, index) to less than the size of the string
- Appending the remaining characters to the current subset
- Make the recursive call for the next index.
- Once all subsets beginning with the initial “curr” are printed, remove the last character to consider a different prefix of subsets.

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 = -1, string curr = "") 
{ 
    int n = str.length(); 
  
    // base case 
    if (index == n) 
        return; 
  
    // First print current subset 
    cout << curr << "\n"; 
  
    // Try appending remaining characters 
    // to current subset 
    for (int i = index + 1; i < n; i++) { 
  
        curr += str[i]; 
        powerSet(str, i, curr); 
  
        // Once all subsets beginning with 
        // initial "curr" are printed, remove 
        // last character to consider a different 
        // prefix of subsets. 
        curr.erase(curr.size() - 1); 
    } 
    return; 
} 
  
// Driver code 
int main() 
{ 
    string str = "abc"; 
    powerSet(str); 
    return 0; 
}

Java

// Java program to generate power set 
import java.util.*; 
  
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) { 
            return; 
        } 
  
        // First print current subset 
        System.out.println(curr); 
  
        // Try appending remaining characters 
        // to current subset 
        for (int i = index + 1; i < n; i++) { 
            curr += str.charAt(i); 
            powerSet(str, i, curr); 
  
            // Once all subsets beginning with 
            // initial "curr" are printed, remove 
            // last character to consider a different 
            // prefix of subsets. 
            curr = curr.substring(0, curr.length() - 1); 
        } 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        String str = "abc"; 
        int index = -1; 
        String curr = ""; 
        powerSet(str, index, curr); 
    } 
} 
  
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to generate power set 
  
# str : Stores input string 
# curr : Stores current subset 
# index : Index in current subset, curr 
  
  
def powerSet(str1, index, curr): 
    n = len(str1) 
  
    # base case 
    if (index == n): 
        return
  
    # First print current subset 
    print(curr) 
  
    # Try appending remaining characters 
    # to current subset 
    for i in range(index + 1, n): 
        curr += str1[i] 
        powerSet(str1, i, curr) 
  
        # Once all subsets beginning with 
        # initial "curr" are printed, remove 
        # last character to consider a different 
        # prefix of subsets. 
        curr = curr.replace(curr[len(curr) - 1], "") 
  
    return
  
  
# Driver code 
if __name__ == '__main__': 
    str = "abc"
    powerSet(str, -1, "") 
  
# This code is contributed by 
# Surendra_Gangwar 

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) { 
            return; 
        } 
  
        // First print current subset 
        Console.WriteLine(curr); 
  
        // Try appending remaining characters 
        // to current subset 
        for (int i = index + 1; i < n; i++) { 
            curr += str[i]; 
            powerSet(str, i, curr); 
  
            // Once all subsets beginning with 
            // initial "curr" are printed, remove 
            // last character to consider a different 
            // prefix of subsets. 
            curr = curr.Substring(0, curr.Length - 1); 
        } 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        string str = "abc"; 
        int index = -1; 
        string curr = ""; 
        powerSet(str, index, curr); 
    } 
} 
  
// This code is contributed by Ita_c.

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) 
        { 
            return; 
        } 
    
        // First print current subset  
        document.write(curr+"<br>"); 
    
        // Try appending remaining characters  
        // to current subset  
        for (let i = index + 1; i < n; i++)  
        { 
            curr += str[i]; 
            powerSet(str, i, curr); 
    
            // Once all subsets beginning with  
            // initial "curr" are printed, remove  
            // last character to consider a different  
            // prefix of subsets.  
            curr = curr.substring(0, curr.length - 1); 
        } 
    } 
      
    // Driver code  
    let str = "abc"; 
    let index = -1; 
    let curr = ""; 
    powerSet(str, index, curr); 
      
      
    // This code is contributed by rag2127 
</script>

Output

a
ab
abc
ac
b
bc
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