Combinations - C++ Solution

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]}.