Given an array arr[] of N integers, the task is to find the Kth lexicographically smallest subset of the given array.
Example:
Input: arr[] = {5, 15}, K = 2
Output: 5 15
Explanation: The subsets of the given set in lexicographic order are {5}, {5, 15}, and {15}. Hence the 2nd smallest subset is {5, 15}.Input: arr[] = {1, 2, 3, 4}, K = 5
Output: 1 2 4
Approach: The given problem can be solved by generating all the power set of the given array and thereafter sorting the subsets of the power set in lexicographic order. Hence, the subset at the Kth index of the sorted power set is the required answer.
Below is the implementation of the above approach:
C++
// 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 << " " ; } } |
Java
import java.util.*; class Main { // Function to find the power set of the // given array static List<List<Integer>> powerSet( int [] arr, int N) { int pow1 = ( int ) Math.pow( 2 , N); // Stores the power set List<List<Integer>> v = new ArrayList<>(); // Loop to iterate over all elements of // the power set for ( int count = 0 ; count < pow1; count++) { // Stores the current subset List<Integer> temp = new ArrayList<>(); for ( int j = 0 ; j < N; j++) { if ((count & ( 1 << j)) != 0 ) { temp.add(arr[j]); } } // Sorting the current subset Collections.sort(temp); if (count != 0 ) { v.add(temp); } } // Return Power Set return v; } // Function to find the // Kth lexicographic smallest // subset of the given array static List<Integer> kthSmallestSubset( int [] arr, int N, int K) { // Stores the power set List<List<Integer>> powSet = powerSet(arr, N); // Sort the power set // in lexicographic order Collections.sort(powSet, new LexicographicComparator()); // Return Answer return powSet.get(K - 1 ); } public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 }; int N = arr.length; int K = 5 ; List<Integer> ans = kthSmallestSubset(arr, N, K); for ( int x : ans) { System.out.print(x + " " ); } } static class LexicographicComparator implements Comparator<List<Integer>> { public int compare(List<Integer> a, List<Integer> b) { int n = a.size(), m = b.size(); for ( int i = 0 ; i < n && i < m; i++) { if (a.get(i) != b.get(i)) return a.get(i) - b.get(i); } return n - m; } } } |
Python3
# 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. |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the power set of the given array static List<List< int > > PowerSet( int [] arr, int N) { int pow1 = ( int )Math.Pow(2, N); // Stores the power set List<List< int > > v = new List<List< int > >(); // Loop to iterate over all elements of the power // set for ( int count = 0; count < pow1; count++) { // Stores the current subset List< int > temp = new List< int >(); for ( int j = 0; j < N; j++) { if ((count & (1 << j)) != 0) { temp.Add(arr[j]); } } // Sorting the current subset temp.Sort(); if (count != 0) { v.Add(temp); } } // Return Power Set return v; } // Function to find the Kth lexicographic smallest // subset of the given array static List< int > KthSmallestSubset( int [] arr, int N, int K) { // Stores the power set List<List< int > > powSet = PowerSet(arr, N); // Sort the power set in lexicographic order powSet.Sort( new LexicographicComparer()); // Return Answer return powSet[K - 1]; } static public void Main() { // Code int [] arr = { 1, 2, 3, 4 }; int N = arr.Length; int K = 5; List< int > ans = KthSmallestSubset(arr, N, K); foreach ( int x in ans) { Console.Write(x + " " ); } } } class LexicographicComparer : IComparer<List< int > > { public int Compare(List< int > a, List< int > b) { int n = a.Count, m = b.Count; for ( int i = 0; i < n && i < m; i++) { if (a[i] != b[i]) { return a[i] - b[i]; } } return n - m; } } // This code is contributed by lokeshmvs21. |
Javascript
<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
Time Complexity: O(N * 2N)
Auxiliary Space: O(2N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!