Dado un conjunto representado como una string, escriba un código recursivo para imprimir todos los subconjuntos del mismo. Los subconjuntos se pueden imprimir en cualquier orden.
Ejemplos:
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"
Método 1: la idea es fijar un prefijo, generar todos los subconjuntos que comiencen con el prefijo actual. Después de generar todos los subconjuntos con un prefijo, reemplace el último carácter con uno de los caracteres restantes.
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>
Producción:
a ab abc ac b bc c
Método 2: La idea es considerar dos casos para cada personaje. (i) Considerar el carácter actual como parte del subconjunto actual (ii) No considerar el carácter actual como parte del subconjunto actual.
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>
Producción:
abc ab ac a bc b c
Método 3: la idea es elegir cada elemento uno por uno del conjunto de entrada, luego generar un subconjunto para el mismo, y seguimos este proceso recursivamente.
Usaremos ArrayList para este propósito
. Por ejemplo,
f(0) = {a}, {} // {} cuando no incluimos ningún elemento del conjunto, es nulo, es decir, {}.
f(1) = {a}, {}, {b}, {a, b} // Tenemos que copiar todos los elementos de f(0) y luego incluir el siguiente elemento del conjunto, es decir, b. Entonces f(1) = f(0) + 1;
f(2) = {a}, {}, {b}, {a, b}, {a, c}, {c}, {b, c}, {a, b, c}. Entonces f(2) = f(1) +2;
La forma general se convierte en f(n) = f(n-1) + n;
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;
}
}
Producción:
[[], [a], [b], [a, b], , [a, c], [b, c], [a, b, c]]