CareerCup

The easiest way to see this example is to note that it is just a special case of a combination. Here is a solution that will print out the results of the subsets as specified. The easiest way to do combinations is via recursion, hence my solution uses recursion. It is written in C++, and tested using g++ compiler on Linux.

#include <vector>
#include <iostream>

using namespace std;

//Will construct the subsets
void subsets(const int* arr, int start, int size, int k, vector<int>& res, vector<int>& prfx) {
    if (!k) {
        for (int j=0; j < prfx.size(); j++)
            res.push_back(prfx[j]);
        return;
    }

    for (int i=start; i < size; i++) {
        prfx.push_back(arr[i]);
        if (k)
            subsets(arr, i+1, size, k-1, res, prfx);

        prfx.pop_back();
    }
}

//Helper function to call the recursive function
void subsets(const int* arr, int size, int k) {
    vector<int> result;
    vector<int> prfx;
    subsets(arr, 0, size, k, result, prfx);
    int *ans = new int[result.size()];

    int t =0;
    for (int i=0; i < result.size(); i++) {
        if (!t)
            cout <<"{";

        if (t != k-1)
            cout << result[i] <<",";
        else
            cout << result[i];

        if (t== k-1) {
            cout <<"},";
            t=0;
        } else t++;

    }

    cout << endl;
}


int main	{
    int ss[6] = {1,2,3,4,5, 6};
 
    subsets(ss, 6, 2); //subsets with size 2
    subsets(ss, 6, 3); //subsets with size 3
    return 0;
}

vector returnSubsets(vector items, int k) {
	int[] result;
	if (k < 1 || items.length < k) {
		return null;
	}
	if (k == 1) {
		return items;
	}
	if (items.length == k) {
		vector result = createSetFromItems(items)
	}
	for (int i=0;i<items.length;i++) {
		vector exceptItems = getItemsExcept(items, i);
		vector result;
		result += returnSubsets(exceptItems, k);
		result += mergeItem(items[k], returnSubsets(exceptItems, k-1));
		return result;
	}
}

private static ArrayList<ArrayList<Integer>> findSubArrays(Integer subArraySize, ArrayList<Integer> array) {
		ArrayList<ArrayList<Integer>> subArray = new ArrayList<ArrayList<Integer>>();
		
		int i=0;
		while ((i+subArraySize)<=  array.size()){
			for (int j=i; j<=(array.size() - subArraySize); j++){
				ArrayList<Integer> aSubArray = new ArrayList<Integer>();
				aSubArray.add(array.get(i));
				for (int k=1; k<subArraySize; k++){
					aSubArray.add(array.get(j+k));
				}
				subArray.add(aSubArray);
			}
			i++;
		}
		return subArray;
	}

#include <iostream>

using namespace std;

// function to increment the counters
int inc(int i, int a[], int n,int k)
{
	if (i<=0)
	{
		return (++a[0]);
	}
	a[i]++;
	if(a[i] >= (n - (k-i)))
	{
		a[i] = inc(i-1, a, n, k) + 1;
	}
	return a[i];
}

// function to check the end of loop
bool end_of_loop(int a[], int k, int n)
{
	bool res = true;
	for(int i = 0; i < k; i++)
	{
		res = res && (a[i] >= (n -(k+i-1)));
	}
	return res;
}


int main()
{
	// input array
	int arr[] = {1,2,3,4,5,6,7,8};
	// total number of elements in array
	int N = 8;
	// combination size 
	int K = 4;

	// indexes of size K
	int a[K];

	for(int i = 0; i<K;i++)
	{
		a[i] = i;
	}

	bool loop = end_of_loop(arr,K,N-1);
	int count = 0;
	//loop till all combinations are printed
	while(!loop)
	{
		for(int i = 0; i < K; i++)
		{
			cout << arr[a[i]] <<" - ";
		}
		cout <<endl;
		count++;
		// increment the counters
		inc(K-1, a, N,K-1);

		// check for end of loop
		loop = end_of_loop(a,K,N-1);
	}

	// total no of combinations
	cout << "Count -- "<<count<<endl;
	return 0;

}