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]}.
Comments
Post a Comment