TCS CodeVita Mock Test Coding Question 6

#include < iostream>
#include < vector>
#include < algorithm>

using namespace std;

// Function to generate all possible legal subsets
vector> generateSubsets(vector &strings) {
    vector< vector> subsets;
    int n = strings.size();
    
    // Rank 1: Empty set
    subsets.push_back({});

    // Ranks 2 to N+1: Individual strings
    for (int i = 0; i < n; i++) {
        subsets.push_back({strings[i]});
    }

    // Generate combinations of strings to form subsets
    for (int subsetSize = 2; subsetSize <= n; subsetSize++) {
        do {
            bool validCombination = true;
            for (int i = 0; i < subsetSize - 1; i++) {
                if (find(strings.begin(), strings.end(), subsets.back()[i]) > find(strings.begin(), strings.end(), subsets.back()[i + 1])) {
                    validCombination = false;
                    break;
                }
            }
            if (validCombination) {
                subsets.push_back({});
                for (int i = 0; i < subsetSize; i++) {
                    subsets.back().push_back(strings[i]);
                }
            }
        } while (next_permutation(strings.begin(), strings.end()));
    }

    return subsets;
}

int main() {
    int N;
    cin >> N;
    int R;
    cin >> R;
    cin.ignore();
    
    string inputStr;
    getline(cin, inputStr);
    
    vector strings;
    size_t pos = 0;
    while ((pos = inputStr.find(',')) != string::npos) {
        strings.push_back(inputStr.substr(0, pos));
        inputStr.erase(0, pos + 1);
    }
    strings.push_back(inputStr);

    // Generate all legal subsets
    vector> subsets = generateSubsets(strings);

    // Find and print the subset corresponding to rank R
    if (R <= subsets.size()) {
        vector result = subsets[R - 1];
        for (const string &s : result) {
            cout << s;
            if (&s != &result.back()) {
                cout << ',';
            }
        }
        cout << endl;
    } else {
        cout << "Rank exceeds the number of subsets." << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int R = scanner.nextInt();
        scanner.nextLine();
        String[] strings = scanner.nextLine().split(",");
        List< List< String>> subsets = generateSubsets(strings);
        if (R <= subsets.size()) {
            List< String> result = subsets.get(R - 1);
            System.out.println(String.join(",", result));
        } else {
            System.out.println("Rank exceeds the number of subsets.");
        }
    }
    public static List<  List> generateSubsets(String[] strings) {
        List< List< String>> subsets = new ArrayList<>();
        int n = strings.length;
        subsets.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            subsets.add(Collections.singletonList(strings[i]));
        }
        for (int subsetSize = 2; subsetSize <= n; subsetSize++) {
            List< List< String>> combinations = getCombinations(strings, subsetSize);
            for (List< String> combination : combinations) {
                boolean validCombination = true;
                for (int i = 0; i < combination.size() - 1; i++) {
                    if (Arrays.asList(strings).indexOf(combination.get(i)) > Arrays.asList(strings).indexOf(combination.get(i + 1))) {
                        validCombination = false;
                        break;
                    }
                }
                if (validCombination) {
                    subsets.add(new ArrayList<>(combination));
                }
            }
        }
        return subsets;
    }
    public static List< List> getCombinations(String[] strings, int subsetSize) {
        List< List> combinations = new ArrayList<>();
        generateCombinations(strings, subsetSize, 0, new ArrayList<>(), combinations);
        return combinations;
    }
    public static void generateCombinations(String[] strings, int subsetSize, int index, List< String> currentCombination, List< List> combinations) {
        if (subsetSize == 0) {
            combinations.add(new ArrayList<>(currentCombination));
            return;
        }
        if (index >= strings.length) {
            return;
        }
        currentCombination.add(strings[index]);
        generateCombinations(strings, subsetSize - 1, index + 1, currentCombination, combinations);
        currentCombination.remove(currentCombination.size() - 1);
        generateCombinations(strings, subsetSize, index + 1, currentCombination, combinations);
    }
}

import itertools

def generate_subsets(strings):
    subsets = []
    n = len(strings)
    
    subsets.append([])

    for i in range(n):
        subsets.append([strings[i]])

    for subset_size in range(2, n + 1):
        combinations = itertools.combinations(strings, subset_size)
        for combination in combinations:
            valid_combination = True
            for i in range(len(combination) - 1):
                if strings.index(combination[i]) > strings.index(combination[i+1]):
                    valid_combination = False
                    break
            if valid_combination:
                subsets.append(list(combination))

    return subsets

N = int(input())
R = int(input())
strings = input().split(',')

subsets = generate_subsets(strings)

if R <= len(subsets):
    result = subsets[R - 1]
    print(','.join(result))
else:
    print("Rank exceeds the number of subsets.")