There is a set contains N no. of unsorted characters. You have to find out the power sets in lexicographic order of a given set of numbers and print them

belongs to collection: interview C++ coding problems/challenges | Backtracking

mahmoud2506

Save to bookmark

2022-05-01

241

Power Set in Lexicographic order

There is a set contains N no. of unsorted characters. You have to find out the power sets in lexicographic order of a given set of numbers and print them.

    Input:
    Test case T
    //T no. of line with the value of N and corresponding values.
    
    E.g.
    2
    4
    d c b a

    2 
    f u

    1<=T<=100
    1<=N<=1000

    Output:
    Print the power subsets of the set in lexicographic order.

Example

    T=2

    N=4
    d c b a

    Output:
    a
    a b
    a b c
    a b c d
    a b d
    a c
    a c d
    a d
    b
    b c
    b c d
    b d
    c
    c d
    d 

    N=2 
    f u

    Output:
    f
    f u
    u

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

Here we use the vector STL to store the subsets.

    traverse(arr, n, current_pos,set,subset){
        if(Current_pos is greater or equals to the n)Then
            return
        end if

        for i= current_pos to the end of the set
            insert the element of arr[i] into subset
            insert the subset into the set
            traverse(arr,n,i+1,set,subset)
            pop the element from subset
        end for
    }

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

void traverse(char* arr, int n, int pos, vector<vector<char> >& v, vector<char> vi)
{
    //if the current position is greater than or equals to n
    if (pos >= n)
        return;
    for (int i = pos; i < n; i++) {
        vi.push_back(arr[i]);
        v.push_back(vi);
        traverse(arr, n, i + 1, v, vi);
        vi.pop_back();
    }
}

vector<vector<char> > find_subset(char* arr, int n)
{
    vector<vector<char> > v;
    vector<char> vi;
    int pos = 0;
    traverse(arr, n, pos, v, vi);
    return v;
}

void print(vector<vector<char> > v)
{
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        int n;

        cout << "Enter the value of n : ";
        cin >> n;

        char arr[n];

        //taking the set elements
        cout << "Enter the values : ";
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        //sort the elements
        sort(arr, arr + n);

        vector<vector<char> > v = find_subset(arr, n);

        //print the vector
        print(v);
    }
    return 0;
}

Output

Test Case : 2
Enter the value of n : 4
Enter the values : d c b a
a
a b
a b c
a b c d
a b d
a c
a c d
a d
b
b c
b c d
b d
c
c d
d
Enter the value of n : 2
Enter the values : f u
f
f u
u

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)