competitive_programming/backtracking.cpp at main · costadev00/competitive_programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

const int MAXN = 20; // Maior quantidade de elementos que esperamos ler

int n;

void backtracking(int i, bool choosed[])
{
    if (i == n) // Nós já escolhemos para todos os números se eles estarão na resposta ou não
    {
        for (int j = 0; j < n; j++) // Imprimindo a resposta atual
            if (choosed[j])
                cout << j << " ";

        cout << endl;
        return;
    }

    choosed[i] = false;
    backtracking(i + 1, choosed); // Não escolher i na resposta atual

    choosed[i] = true;
    backtracking(i + 1, choosed); // Escolher i na resposta atual
}

int main()
{
    bool choosed[MAXN];

    // Ler o tamanho do conjunto
    cin >> n;
    cout << "Todos os subconjuntos: " << endl;

    backtracking(0, choosed);
}