#include <iostream>
using namespace std;
// Function to print all distinct combinations of length k
void recurse(int arr[], string out, int i, int n, int k)
{
// invalid input
if (k > n)
return;
// base case: combination size is k
if (k == 0) {
cout << out << endl;
return;
}
// start from next index till last index
for (int j = i; j < n; j++)
{
// add current element arr[j] to solution & recurse for next index
// (j+1) with one less element (k-1)
recurse(arr, out + " " + to_string(arr[j]) , j + 1, n, k - 1);
// uncomment below code to handle duplicates
// while (j < n - 1 && arr[j] == arr[j + 1])
// j++;
}
}
// Find all distinct combinations of given length
int main()
{
int arr[] = { 10, 9, 10, 9, 10 };
int k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
// if array contains repeated elements,
// sort the array to handle duplicate combinations
// sort (arr, arr + n);
// process elements from left to right
recurse(arr, "", 0, n, k);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcHJpbnQgYWxsIGRpc3RpbmN0IGNvbWJpbmF0aW9ucyBvZiBsZW5ndGggawp2b2lkIHJlY3Vyc2UoaW50IGFycltdLCBzdHJpbmcgb3V0LCBpbnQgaSwgaW50IG4sIGludCBrKQp7CiAgICAvLyBpbnZhbGlkIGlucHV0CiAgICBpZiAoayA+IG4pCiAgICAgICAgcmV0dXJuOwoKICAgIC8vIGJhc2UgY2FzZTogY29tYmluYXRpb24gc2l6ZSBpcyBrIAogICAgaWYgKGsgPT0gMCkgewogICAgICAgIGNvdXQgPDwgb3V0IDw8IGVuZGw7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgCiAgICAvLyBzdGFydCBmcm9tIG5leHQgaW5kZXggdGlsbCBsYXN0IGluZGV4CiAgICBmb3IgKGludCBqID0gaTsgaiA8IG47IGorKykKICAgIHsKICAgICAgICAvLyBhZGQgY3VycmVudCBlbGVtZW50IGFycltqXSB0byBzb2x1dGlvbiAmIHJlY3Vyc2UgZm9yIG5leHQgaW5kZXgKICAgICAgICAvLyAoaisxKSB3aXRoIG9uZSBsZXNzIGVsZW1lbnQgKGstMSkKICAgICAgICByZWN1cnNlKGFyciwgb3V0ICsgIiAiICsgdG9fc3RyaW5nKGFycltqXSkgLCBqICsgMSwgbiwgayAtIDEpOwoKICAgICAgICAvLyB1bmNvbW1lbnQgYmVsb3cgY29kZSB0byBoYW5kbGUgZHVwbGljYXRlcwogICAgICAgIC8vIHdoaWxlIChqIDwgbiAtIDEgJiYgYXJyW2pdID09IGFycltqICsgMV0pCiAgICAgICAgLy8gICAgaisrOwogICAgfQp9CgovLyBGaW5kIGFsbCBkaXN0aW5jdCBjb21iaW5hdGlvbnMgb2YgZ2l2ZW4gbGVuZ3RoCmludCBtYWluKCkKewogICAgaW50IGFycltdID0geyAxMCwgOSwgMTAsIDksIDEwIH07CiAgICBpbnQgayA9IDU7CgogICAgaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKICAgIC8vIGlmIGFycmF5IGNvbnRhaW5zIHJlcGVhdGVkIGVsZW1lbnRzLAogICAgLy8gc29ydCB0aGUgYXJyYXkgdG8gaGFuZGxlIGR1cGxpY2F0ZSBjb21iaW5hdGlvbnMgCiAgICAvLyBzb3J0IChhcnIsIGFyciArIG4pOwoKICAgIC8vIHByb2Nlc3MgZWxlbWVudHMgZnJvbSBsZWZ0IHRvIHJpZ2h0CiAgICByZWN1cnNlKGFyciwgIiIsIDAsIG4sIGspOwoKICAgIHJldHVybiAwOwp9