# 1. Introduction

In this post, we explore a common problem in combinatorics and algorithm design - generating all distinct combinations of a given length from an integer array. This problem is a classic example of using backtracking to explore all possible combinations in a set.

## Problem

Given an integer array, the task is to find all distinct combinations of a given length k. The combinations should preserve the relative order of elements as they appear in the array. The solution should return a set containing these combinations.

# 2. Solution Steps

1. Use a recursive function to generate combinations.

2. Maintain a current combination vector and add elements to it according to the required length k.

3. Ensure the preservation of the relative order of elements from the original array.

4. Once a combination of length k is formed, add it to the set.

5. Use backtracking to explore all possible combinations.

6. Return the set of combinations.

# 3. Code Program

``````#include <iostream>
#include <vector>
#include <set>
using namespace std;

void findCombinations(const vector<int>& arr, int k, vector<int>& curr, int start, set<vector<int>>& combinations) {
if (curr.size() == k) {
combinations.insert(curr);
return;
}

for (int i = start; i < arr.size(); ++i) {
curr.push_back(arr[i]);
findCombinations(arr, k, curr, i + 1, combinations);
curr.pop_back(); // Backtrack
}
}

set<vector<int>> generateCombinations(const vector<int>& arr, int k) {
set<vector<int>> combinations;
vector<int> curr;
findCombinations(arr, k, curr, 0, combinations);
return combinations;
}

int main() {
vector<int> arr = {2, 3, 4};
int k = 2;
set<vector<int>> result = generateCombinations(arr, k);

// Output the combinations
for (const auto& combo : result) {
cout << "{";
for (int num : combo) {
cout << num << " ";
}
cout << "}\n";
}

return 0;
}

``````

### Output:

```{2 3 }
{2 4 }
{3 4 }
```

### Explanation:

The function generateCombinations finds all distinct combinations of length k from the given array. It uses a recursive approach to build combinations one element at a time while maintaining their order. The backtracking ensures all possible combinations are explored without repetition. For the input array [2, 3, 4] and k = 2, the distinct combinations are {[2, 3], [2, 4], [3, 4]}.