generate all subsets of size k from a set

Question

I want to generate all the subsets of size k from a set.

eg:-say I have a set of 6 elements, I have to list all the subsets in which the cardinality of elements is 3.

I tried looking for solution,but those are code snippets. Its been long since I have done coding,so I find it hard to understand the code and construct a executable program around it.

A complete executable program in C or C++ will be quite helpful. Hoping of an optimal solution using recursion.

Answer 1

The Problem can be solved using recursion. We need to consider the following cases for recursion.

1. The current element is chosen . Now we recursively choose the remaining k-1 elements from the remaining set .(inclusion)
2. The current element is not chosen . Now we recursively choose k elements from the remaining set.(exclusion)

Following is a C++ program that demonstrates the above Algorithm.

#include<iostream>
#include<vector>

using namespace std;    

void computeSubsets(vector<vector<int> > & results, vector<int> const& nums, vector<int> & curSet, int idx, int size) {
    
    if (idx == size) {
        results.push_back(curSet);
        return ;
    }
    
    // Include
    curSet.push_back(nums[idx]);
    computeSubsets(results, nums, curSet, idx+1, size);
    curSet.pop_back();
    
    // Exclude
    computeSubsets(results, nums, curSet, idx+1, size);
}


vector<vector<int>> getSubsets(vector<int> const& nums) {
    vector<vector<int> > results;
    vector<int> temp;
    int size = nums.size();
    
    temp.reserve(size);
    results.reserve(1 << size);
    
    computeSubsets(results, nums, temp,  0, size);
    
    return results;
    
}

int main(){

    vector<int> nums = {1, 2, 3};
    auto subsets = getSubsets(nums);
    for (auto const& subset : subsets) {
        for (auto const& x : subset) {
            cout << x << " ";
        }
        cout << "\n";
    }

    return 0;
}