Conjunto de potencia en orden lexicográfico

Este artículo trata sobre la generación de conjuntos de potencia en orden lexicográfico. 
Ejemplos: 
 

Input : abc
Output : a ab abc ac b bc c

La idea es ordenar la array primero. Después de ordenar, corrige los caracteres uno por uno y genera recursivamente todos los subconjuntos a partir de ellos. Después de cada llamada recursiva, eliminamos el último carácter para que se pueda generar la siguiente permutación. 
 

// CPP program to generate power set in
// lexicographic order.
#include <bits/stdc++.h>
using namespace std;
 
// str : Stores input string
// n : Length of str.
void func(string s, vector<string>& str, int n, int pow_set)
{
    int i, j;
    for (i = 0; i < pow_set; i++) {
        string x;
        for (j = 0; j < n; j++) {
            if (i & 1 << j) {
                x = x + s[j];
            }
        }
        if (i != 0)
            str.push_back(x);
    }
}
int main()
{
    int n;
    string s;
    vector<string> str;
    s = "cab";
    n = s.length();
    int pow_set = pow(2, n);
    func(s, str, n, pow_set);
    sort(str.begin(), str.end());
    for (int i = 0; i < str.size(); i++)
        cout << str[i] << " ";
    cout << endl;
 
    return 0;
}

// Java program to generate power set in
// lexicographic order.
import java.util.*;
 
class GFG {
 
    // str : Stores input string
    // n : Length of str.
    // curr : Stores current permutation
    // index : Index in current permutation, curr
    static void permuteRec(String str, int n,
                           int index, String curr)
    {
        // base case
        if (index == n) {
            return;
        }
        System.out.println(curr);
        for (int i = index + 1; i < n; i++) {
 
            curr += str.charAt(i);
            permuteRec(str, n, i, curr);
 
            // backtracking
            curr = curr.substring(0, curr.length() - 1);
        }
        return;
    }
 
    // Generates power set in lexicographic
    // order.
    static void powerSet(String str)
    {
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        permuteRec(new String(arr), str.length(), -1, "");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "cab";
        powerSet(str);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program to generate power
# set in lexicographic order.
 
# str : Stores input string
# n : Length of str.
# curr : Stores current permutation
# index : Index in current permutation, curr
def permuteRec(string, n, index = -1, curr = ""):
 
    # base case
    if index == n:
        return
 
    if len(curr) > 0:
        print(curr)
 
    for i in range(index + 1, n):
        curr += string[i]
        permuteRec(string, n, i, curr)
 
        # backtracking
        curr = curr[:len(curr) - 1]
 
# Generates power set in lexicographic order
def powerSet(string):
    string = ''.join(sorted(string))
    permuteRec(string, len(string))
 
# Driver Code
if __name__ == "__main__":
    string = "cab"
    powerSet(string)
 
# This code is contributed by vibhu4agarwal

// C# program to generate power set in
// lexicographic order.
using System;
 
class GFG {
 
    // str : Stores input string
    // n : Length of str.
    // curr : Stores current permutation
    // index : Index in current permutation, curr
    static void permuteRec(String str, int n,
                           int index, String curr)
    {
        // base case
        if (index == n) {
            return;
        }
        Console.WriteLine(curr);
        for (int i = index + 1; i < n; i++) {
 
            curr += str[i];
            permuteRec(str, n, i, curr);
 
            // backtracking
            curr = curr.Substring(0, curr.Length - 1);
        }
        return;
    }
 
    // Generates power set in lexicographic
    // order.
    static void powerSet(String str)
    {
        char[] arr = str.ToCharArray();
        Array.Sort(arr);
        permuteRec(new String(arr), str.Length, -1, "");
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str = "cab";
        powerSet(str);
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to generate power
// set in lexicographic order.
 
// str : Stores input string
// n : Length of str.
// curr : Stores current permutation
// index : Index in current permutation, curr
function permuteRec($str, $n, $index = -1,
                              $curr = "")
{
    // base case
    if ($index == $n)
        return;
 
    echo $curr."\n";
    for ($i = $index + 1; $i < $n; $i++)
    {
 
        $curr=$curr.$str[$i];
        permuteRec($str, $n, $i, $curr);
 
        // backtracking
        $curr ="";
    }
    return;
}
 
// Generates power set in lexicographic
// order.
function powerSet($str)
{
 
    $str = str_split($str);
    sort($str);
    permuteRec($str, sizeof($str));
}
 
// Driver code
$str = "cab";
powerSet($str);
 
// This code is contributed by Mithun Kumar
?>

<script>
// javascript program to generate power set in
// lexicographic order.
 
    // str : Stores input string
    // n : Length of str.
    // curr : Stores current permutation
    // index : Index in current permutation, curr
    function permuteRec( str , n , index,  curr) {
        // base case
        if (index == n) {
            return;
        }
        document.write(curr+" ");
        for (var i = index + 1; i < n; i++) {
 
            curr += str[i];
            permuteRec(str, n, i, curr);
 
            // backtracking
            curr = curr.substring(0, curr.length - 1);
        }
        return;
    }
 
    // Generates power set in lexicographic
    // order.
    function powerSet(str) {
        var arr = str.split("");
        arr.sort();
        permuteRec(arr, str.length, -1, "");
    }
 
    // Driver code
     
        var str = "cab";
        powerSet(str);
 
// This code contributed by umadevi9616
</script>

a ab b c ca cab cb 

Complejidad de tiempo : O(n*2 ⁿ ) 
Espacio auxiliar : O(1)