Generating subsets algorithm

I can't imagine a worse solution to this problem, it is slow and is of interest only for studying recursion.

The enumeration of all subsets in Olympiad programming is most often performed by the method of representing an integer variable in binary form (unless there is a special reason to do otherwise). Let's say your set is an array of numbers:

const size_t N = 4;
int A[N] = {1, 2, 3, 1};

Next, you need some variable that will run from 0 to 2**N-1. Let's say, here so:

for (size_t k=0; k<(1llu<<N); ++k) {
  ...
}

Now the set of bits in the variable k at each iteration of this loop will denote a certain subset. Let's say at some step k=5. This means that in binary form (if we have N = 4 bits only needed) it has the form 0101. So you only need to take the elements A with the numbers 0 and 2: {1, 3}. You can do it like this (you need to enter it instead of ... in the previous loop):

size_t n = 0;
for (size_t i=0, j=1; i<N; ++i, j<<=1) {
  if (k&j)  B[n++] = A[i];  
}
// Тут обрабатываем массив `B` из `n` элементов - это и есть наше очередное подмножество.

That's all, so the brute force itself is a subset the computer does it for you when you add 1 to the number k. You only need to take single bits from k and be happy. After looping through i, you have an array B, and the number n is the number of elements in it.

Don't forget that there are two extreme cases here: an empty set and when B=A. You can remove them by changing the boundaries of the loop execution by k like this:

for (size_t k=1; k<(1llu<<N)-1; ++k) {
  ...
}

But then it is no longer possible to make N less than 2, because it will not turn out what you wanted.

The code you provided is intended to generate a set of indexes of elements of a subset. Using the indexes in the vector subset, you will already access your "set" (meaning that the set is represented by an array) and process it in a way that is known to you alone.

That is, for this algorithm, it does not matter at all what is stored in your set and how you will process the subsets. The above algorithm is completely abstracted from this. only generates index sets for you, and everything else is your task. Therefore, it "does not refer to the elements of the set". This you must add to it yourself.

If you use the four-element set { 1, 2, 3, 1 } as the" set", then for the algorithm it is just an ordered four-element set, no different from { "вася", "коля", "миша", "лена" }. The algorithm will correctly generate "subsets" for this set, just like for any other set of size 4. Of course, from the point of view of in this approach, the two 1 in your set are considered "different".

There is no condition that there are no duplicate elements. So you can change it this way. Now there is a connection with the elements of the set.

void search(vector<int> set, vector<int> subset, int n, int k){
if (k == n + 1){
    print(subset);
} else{
    subset.push_back(set[k]);
    search(set, subset, n, k+1);
    subset.pop_back();
    search(set, subset, n, k+1);
}}

int main() {
vector<int> set = {1, 2, 3, 1};
vector<int> subset;
search(set, subset, 3, 0);
return 0;}