Generar distintas subsecuencias de una string dada en orden lexicográfico

Dada una string s, haga una lista de todas las combinaciones posibles de letras de una string dada S. Si hay dos strings con el mismo conjunto de caracteres, imprima la disposición lexicográficamente más pequeña de las dos strings
Para la string abc, la lista en orden lexicográfico las subsecuencias son, a ab abc ac b bc c

Ejemplos: 

Input : s = "ab"
Output : a ab b

Input  : xyzx
Output : x xx xy xyx xyz xyzx xz xzx y
         yx yz yzx z zx

La idea es usar un conjunto (que se implementa usando BST de equilibrio automático ) para almacenar subsecuencias para que se puedan probar los duplicados.
Para generar todas las subsecuencias, eliminamos uno por uno todos los caracteres y recurrimos para la string restante. 

Implementación:

// C++ program to print all distinct subsequences
// of a string.
#include <bits/stdc++.h>
using namespace std;
 
// Finds and stores result in st for a given
// string s.
void generate(set<string>& st, string s)
{
    if (s.size() == 0)
        return;
 
    // If current string is not already present.
    if (st.find(s) == st.end()) {
        st.insert(s);
 
        // Traverse current string, one by one
        // remove every character and recur.
        for (int i = 0; i < s.size(); i++) {
            string t = s;
            t.erase(i, 1);
            generate(st, t);
        }
    }
    return;
}
 
// Driver code
int main()
{
    string s = "xyz";
    set<string> st;
    set<string>::iterator it;
    generate(st, s);
    for (auto it = st.begin(); it != st.end(); it++)
        cout << *it << endl;
    return 0;
}

// Java program to print all distinct subsequences
// of a string.
import java.util.*;
 
class GFG {
 
    // Finds and stores result in st for a given
    // string s.
    static void generate(Set<String> st, String s)
    {
        if (s.length() == 0) {
            return;
        }
 
        // If current string is not already present.
        if (!st.contains(s)) {
            st.add(s);
 
            // Traverse current string, one by one
            // remove every character and recur.
            for (int i = 0; i < s.length(); i++) {
                String t = s;
                t = t.substring(0, i) + t.substring(i + 1);
                generate(st, t);
            }
        }
        return;
    }
 
    // Driver code
    public static void main(String args[])
    {
        String s = "xyz";
        TreeSet<String> st = new TreeSet<>();
        generate(st, s);
        for (String str : st) {
            System.out.println(str);
        }
    }
}
 
// This code has been contributed by 29AjayKumar
// modified by rahul_107

# Python program to print all distinct
# subsequences of a string.
 
# Finds and stores result in st for a given
# string s.
def generate(st, s):
    if len(s) == 0:
        return
 
    # If current string is not already present.
    if s not in st:
        st.add(s)
 
        # Traverse current string, one by one
        # remove every character and recur.
        for i in range(len(s)):
            t = list(s).copy()
            t.remove(s[i])
            t = ''.join(t)
            generate(st, t)
 
    return
 
 
# Driver Code
if __name__ == "__main__":
    s = "xyz"
    st = set()
    generate(st, s)
    for i in st:
        print(i)
 
# This code is contributed by
# sanjeev2552

// C# program to print all distinct subsequences
// of a string.
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Finds and stores result in st for a given
    // string s.
    static void generate(HashSet<String> st, String s)
    {
        if (s.Length == 0) {
            return;
        }
 
        // If current string is not already present.
        if (!st.Contains(s)) {
            st.Add(s);
 
            // Traverse current string, one by one
            // remove every character and recur.
            for (int i = 0; i < s.Length; i++) {
                String t = s;
                t = t.Substring(0, i) + t.Substring(i + 1);
                generate(st, t);
            }
        }
        return;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String s = "xyz";
        HashSet<String> st = new HashSet<String>();
        generate(st, s);
        foreach(String str in st)
        {
            Console.WriteLine(str);
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// JavaScript program to print
// all distinct subsequences
// of a string.
 
// Finds and stores result in st for a given
// string s.
function generate(st,s){
    if (s.length == 0)
        return st;
 
    // If current string is not already present.
    if (!st.has(s)) {
        st.add(s);
        // Traverse current string, one by one
        // remove every character and recur.
        for (let i = 0; i < s.length; i++) {
            let t = s;
            t = t.substr(0, i) + t.substr(i + 1);
            st = generate(st, t);
        }
    }
    return st;
}
 
// Driver code
let s = "xyz";
 
let st = new Set();
st = generate(st, s);
 
let str = '';
console.log(st)
for(item of st.values())
    str += item + '<br> '
     
document.write(str);
 
</script>

x
xy
xyz
xz
y
yz
z

Complejidad temporal: O(n ⁿ )
Espacio auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi y SANDEEP GAUR MNNIT . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.