Encuentre el subarreglo lexicográficamente más pequeño de Kth

Dada una array arr[] de N enteros, la tarea es encontrar el K ^-ésimo subconjunto lexicográficamente más pequeño de la array dada.

Ejemplo:

Entrada: arr[] = {5, 15}, K = 2
Salida: 5 15
Explicación: Los subconjuntos del conjunto dado en orden lexicográfico son {5}, {5, 15} y {15}. Por lo tanto, el segundo subconjunto más pequeño es {5, 15}.

Entrada: arr[] = {1, 2, 3, 4}, K = 5
Salida: 1 2 4

Enfoque: El problema dado se puede resolver generando todo el conjunto de potencia de la array dada y luego clasificando los subconjuntos del conjunto de potencia en orden lexicográfico . Por lo tanto, el subconjunto en el K ^-ésimo índice del conjunto potencia ordenado es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the power set of the
// given array
vector<vector<int> > powerSet(int* arr, int N)
{
    int pow1 = pow(2, N);
 
    // Stores the power set
    vector<vector<int> > v;
 
    // Loop to iterate over all elements of
    // the power set
    for (int count = 0; count < pow1; count++) {
 
        // Stores the current subset
        vector<int> temp;
        for (int j = 0; j < N; j++) {
            if (count & (1 << j)) {
                temp.push_back(arr[j]);
            }
        }
 
        // Sorting the current subset
        sort(temp.begin(), temp.end());
        if (count != 0) {
            v.push_back(temp);
        }
    }
 
    // Return Power Ser
    return v;
}
 
// Function to find the
// Kth lexicographic smallest
// subset of the given array
vector<int> kthSmallestSubset(
    int* arr, int N, int K)
{
    // Stores the power set
    vector<vector<int> > powSet
        = powerSet(arr, N);
 
    // Sort the power set
    // in lexicographic order
    sort(powSet.begin(), powSet.end());
 
    // Return Answer
    return powSet[K - 1];
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 5;
 
    vector<int> ans
        = kthSmallestSubset(arr, N, K);
    for (auto x : ans) {
        cout << x << " ";
    }
}

# Python Program of the above approach
 
# Function to find the power set of the
# given array
def powerSet(arr, N):
  pow1 = 2 ** N
 
  # Stores the power set
  v = [];
 
  # Loop to iterate over all elements of
  # the power set
  for count in range(pow1):
 
    # Stores the current subset
    temp = []
    for j in range(N):
      if (count & (1 << j)):
        temp.append(arr[j]);
 
    # Sorting the current subset
    temp.sort();
    if (count != 0):
      v.append(temp);
 
  # Return Power Ser
  return v;
 
# Function to find the
# Kth lexicographic smallest
# subset of the given array
def kthSmallestSubset(arr, N, K):
   
  # Stores the power set
  powSet = powerSet(arr, N);
 
  # Sort the power set
  # in lexicographic order
  powSet.sort();
 
  # Return Answer
  return powSet[K - 1];
 
# Driver Code
arr = [1, 2, 3, 4];
N = len(arr)
K = 5;
 
ans = kthSmallestSubset(arr, N, K);
for x in ans:
  print(x, end=" ");
 
  # This code is contributed by gfgking.

<script>
// Javascript Program of the above approach
 
// Function to find the power set of the
// given array
function powerSet(arr, N) {
  let pow1 = Math.pow(2, N);
 
  // Stores the power set
  let v = [];
 
  // Loop to iterate over all elements of
  // the power set
  for (let count = 0; count < pow1; count++) {
 
    // Stores the current subset
    let temp = [];
    for (let j = 0; j < N; j++) {
      if (count & (1 << j)) {
        temp.push(arr[j]);
      }
    }
 
    // Sorting the current subset
    temp.sort();
    if (count != 0) {
      v.push(temp);
    }
  }
 
  // Return Power Ser
  return v;
}
 
// Function to find the
// Kth lexicographic smallest
// subset of the given array
function kthSmallestSubset(arr, N, K) {
  // Stores the power set
  let powSet = powerSet(arr, N);
 
  // Sort the power set
  // in lexicographic order
  powSet.sort();
 
  // Return Answer
  return powSet[K - 1];
}
 
// Driver Code
 
let arr = [1, 2, 3, 4];
let N = arr.length;
let K = 5;
 
let ans = kthSmallestSubset(arr, N, K);
for (x of ans) {
  document.write(x + " ");
}
 
// This code is contributed by gfgking.
</script>

1 2 4 

Complejidad de Tiempo: O(N * 2 ^N )
Espacio Auxiliar: O(2 ^N )