Порождение подмножеств алгоритм

void search(int k){
if (k == n + 1){
    //обработать подмножество
} else{
    //включить k в подмножество
    subset.push_back(k);
    search(k+1);
    subset.pop_back();
    search(k+1);
    //не включить k в подмножество
}}

Более плохого решения этой задачи я и представить не могу, оно медленное и представляет интерес только для изучения рекурсии.

Перечисление всех подмножеств в олимпиадном программировании чаще всего выполняется методом представления целочисленной переменной в двоичном виде (если нет особых причин поступать иначе). Допустим, ваше множество - это массив чисел:

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

Далее вам нужна некая переменная, которая будет бежать от 0 до 2**N-1. Допустим, вот так:

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

Теперь набор битов в переменной k на каждой итерации этого цикла будет обозначать некое подмножество. Допустим, на каком-то шаге k=5. Это означает, что в двоичном виде (если у нас N = 4 бита только нужны) оно имеет вид 0101. Таким образом, вам нужно взять лишь элементы A с номерами 0 и 2: {1, 3}. Сделать это можно так (это нужно вписать вместо ... в предыдущем цикле):

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` элементов - это и есть наше очередное подмножество.

Вот и всё, таким образом, сам по себе перебор подмножество уже за вас делает компьютер, когда вы прибавляете 1 к числу k. Вам нужно только брать единичные биты из k и радоваться. После выполнения цикла по i вы имеете массив B, а число n - это число элементов в нём.

Не забывайте, что здесь имеет место два крайних случая: пустое множество и когда B=A. Их можно убрать, поменяв границы выполнения цикла по k вот так:

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

Но тогда уже нельзя делать N меньше 2, потому что получится не то, что вы хотели.

Нет условия, что повторяющихся элементов нет. Поэтому можно изменить таким образом. Теперь есть связь с элементами множества.

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;}

Приведенный вами код предназначен для генерации набора индексов элементов подмножества. Пользуясь индексами в векторе subset вы уже будете осуществлять доступ к вашему "множеству" (подразумевая, что множество представлено неким массивом) и обрабатывать его одному вам известным способом.

То есть для этого алгоритма совершенно не важно, что хранится в вашем множестве и как вы будете обрабатывать подмножества. Приведенный алгоритм от этого полностью абстрагирован. Он лишь генерирует наборы индексов для вас, а все остальное - ваша задача. Поэтому в нем и "нет обращения к элементам множества". Это вы должны дописать в него сами.

Если вы в качестве "множества" будете использовать четырехэлементный набор { 1, 2, 3, 1 }, то для алгоритма это просто упорядоченный четырехэлементный набор, ничем не отличающийся от { "вася", "коля", "миша", "лена" }. Алгоритм будет исправно генерировать "подмножества" для этого множества, как и для любого другого набора размера 4. Разумеется, с точки зрения этого подхода две 1 в вашем наборе считаются "разными".

Полное решение на с++

using namespace std;
typedef vector<int> vi;
#define PB push_back
void search(int k, int n,vi subset){
   if (k == n+1){
    for(int i = 0 ; i < subset.size(); i++){
        cout << subset[i] << " ";
    }
    cout << endl;
    subset.resize(0);
   }
   else{
    subset.PB(k);
    search(k+1,n,subset);
    subset.pop_back();
    search(k+1,n,subset);
   }

}
int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
   vi subset;
   int n,k;
   n = 3;
   k = 1;
   search(k,n,subset);
   return 0;
}