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

Recursive program to generate power set using Recursion:

The idea is to pick each element one by one from the input set, then generate a subset for the same, and we follow this process recursively.

Follow the steps below to implement the above idea:

The base condition for the recursive call, when the current index becomes negative then add empty list into the allSubsets.
Make recursive call for the current index – 1, then we’ll receive allSubsets list from 0 to index -1
Create a list of list moreSubsets
Iterate over all the subsets that are received from above recursive call
- Copy all the subset into newSubset
- Add the current item into newSubset
- Add newSubset into moreSubsets
Add moreSubsets into allSubsets
Finally, return allSubsets.

Follow the steps below to implement the above approach:

C++

// C++ Recursive code to print 
// all subsets of set using ArrayList 
#include <bits/stdc++.h> 
using namespace std; 
  
vector<vector<string> > getSubset(vector<string> set, 
                                  int index) 
{ 
  vector<vector<string> > allSubsets; 
  if (index < 0) { 
    vector<string> v; 
    allSubsets.push_back(v); 
  } 
  
  else { 
    allSubsets = getSubset(set, index - 1); 
    string item = set[index]; 
    vector<vector<string> > moreSubsets; 
  
    for (vector<string> subset : allSubsets) { 
      vector<string> newSubset; 
      for (auto it : subset) 
        newSubset.push_back(it); 
      newSubset.push_back(item); 
      moreSubsets.push_back(newSubset); 
    } 
    for (auto it : moreSubsets) 
      allSubsets.push_back(it); 
  } 
  return allSubsets; 
} 
int main() 
{ 
  
  vector<string> set = { "a", "b", "c" }; 
  
  int index = set.size() - 1; 
  vector<vector<string> > result = getSubset(set, index); 
  for (auto it : result) { 
    cout << " [ "; 
    for (auto itr : it) { 
      cout << itr << ","; 
    } 
    cout << "],"; 
  } 
} 
  
// This code is contributed by garg28harsh.

Java

// Java Recursive code to print 
// all subsets of set using ArrayList 
import java.util.ArrayList; 
  
public class PowerSet { 
  
    public static void main(String[] args) 
    { 
  
        String[] set = { "a", "b", "c" }; 
  
        int index = set.length - 1; 
        ArrayList<ArrayList<String> > result 
            = getSubset(set, index); 
        System.out.println(result); 
    } 
  
    static ArrayList<ArrayList<String> > 
    getSubset(String[] set, int index) 
    { 
        ArrayList<ArrayList<String> > allSubsets; 
        if (index < 0) { 
            allSubsets 
                = new ArrayList<ArrayList<String> >(); 
            allSubsets.add(new ArrayList<String>()); 
        } 
  
        else { 
            allSubsets = getSubset(set, index - 1); 
            String item = set[index]; 
            ArrayList<ArrayList<String> > moreSubsets 
                = new ArrayList<ArrayList<String> >(); 
  
            for (ArrayList<String> subset : allSubsets) { 
                ArrayList<String> newSubset 
                    = new ArrayList<String>(); 
                newSubset.addAll(subset); 
                newSubset.add(item); 
                moreSubsets.add(newSubset); 
            } 
            allSubsets.addAll(moreSubsets); 
        } 
        return allSubsets; 
    } 
}

Python3

# Python recursive code to print 
# all subsets of set using ArrayList 
  
  
def get_subset(s, index): 
    all_subsets = [] 
    if index < 0: 
        all_subsets.append([]) 
    else: 
        all_subsets = get_subset(s, index-1) 
        item = s[index] 
        more_subsets = [] 
        for subset in all_subsets: 
            new_subset = [] 
            for i in subset: 
                new_subset.append(i) 
            new_subset.append(item) 
            more_subsets.append(new_subset) 
        for i in more_subsets: 
            all_subsets.append(i) 
    return all_subsets 
  
  
# Driver Code 
set = ["a", "b", "c"] 
index = len(set) - 1
result = get_subset(set, index) 
  
for subset in result: 
    print("[", end=" ") 
    for item in subset: 
        print(item, end=" ") 
    print("],", end=" ") 

C#

// c# code for the above approach 
using System; 
using System.Collections.Generic; 
  
namespace Subsets { 
public class GFG { 
    static List<List<string> > GetSubsets(List<string> set, 
                                          int index) 
    { 
        List<List<string> > allSubsets; 
        if (index < 0) { 
            List<string> emptyList = new List<string>(); 
            allSubsets 
                = new List<List<string> >{ emptyList }; 
        } 
        else { 
            allSubsets = GetSubsets(set, index - 1); 
            string item = set[index]; 
            List<List<string> > moreSubsets 
                = new List<List<string> >(); 
            foreach(List<string> subset in allSubsets) 
            { 
                List<string> newSubset = new List<string>(); 
                foreach(string it in subset) 
                { 
                    newSubset.Add(it); 
                } 
                newSubset.Add(item); 
                moreSubsets.Add(newSubset); 
            } 
            foreach(List<string> it in moreSubsets) 
            { 
                allSubsets.Add(it); 
            } 
        } 
        return allSubsets; 
    } 
  
    static void Main(string[] args) 
    { 
        List<string> set
            = new List<string>{ "a", "b", "c" }; 
        int index = set.Count - 1; 
        List<List<string> > result = GetSubsets(set, index); 
        foreach(List<string> it in result) 
        { 
            Console.Write("[ "); 
            foreach(string itr in it) 
            { 
                Console.Write(itr + " "); 
            } 
            Console.Write("], "); 
        } 
    } 
} 
}

Javascript

//javascript code for the above approach 
function getSubset(set, index) { 
  let allSubsets = []; 
  
  if (index < 0) { 
    let v = []; 
    allSubsets.push(v); 
  } else { 
    allSubsets = getSubset(set, index - 1); 
    let item = set[index]; 
    let moreSubsets = []; 
  
    for (let subset of allSubsets) { 
      let newSubset = []; 
      for (let it of subset) 
        newSubset.push(it); 
      newSubset.push(item); 
      moreSubsets.push(newSubset); 
    } 
  
    for (let it of moreSubsets) 
      allSubsets.push(it); 
  } 
    
  return allSubsets; 
} 
  
let set = ["a", "b", "c"]; 
let index = set.length - 1; 
let result = getSubset(set, index); 
  
for (let it of result) { 
  console.log(" [ " + it.join(",") + " ],"); 
} 

Output

[[], [a], [b], [a, b], , [a, c], [b, c], [a, b, c]]

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

Iterative program for the power set.

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