` 1: empty set`

` 2: 10`

` 3: 8`

` 4: 8 10`

` 5: 5`

` 6: 5 10`

` 7: 5 8`

` 8: 5 8 10`

` 9: 2`

` 10: 2 10`

` 11: 2 8`

` 12: 2 8 10`

` 13: 2 5`

` 14: 2 5 10`

` 15: 2 5 8`

` 16: 2 5 8 10`

Well the answer is simple recursively: for each number in the array, compute recursively all the subsets without including it. Then include it and compute again all the subsets.

1: void subsets_recursive(int* vec, int size, int index, vector<int>* subset) {

2: if (index == size) { //print if we reached the end

3: if (subset->size() == 0)

4: cout << "empty set";

5: for (int i = 0; i < subset->size(); i++)

6: cout << subset->at(i) << " ";

` 7: cout << endl;`

8: return;

` 9: }`

10: int n = subset->size();

11: //first print all the subsets without including the number

` 12: subsets_recursive(vec, size, index + 1, subset);`

13: //clear the numbers that we added in the previous subsets

14: while (subset->size() != n)

` 15: subset->pop_back();`

16: //add the number to the subset and print all subsets including it

` 17: subset->push_back(vec[index]);`

` 18: subsets_recursive(vec, size, index + 1, subset);`

` 19: }`

Iteratively it's a different story. Complexity for this (both recursively and iteratively) is O(2

^{n}), where "n" is the size of the array. This means we have to iterate 2

^{n}times. As it turns out, there's a trick involved: take each number i from 0 to 2

^{n}and check each bit. If bit k from number i is 1, then consider array

_{k}to be in the current subset. Too bad I didn't think of this during the interview. Here it is:

1: void subsets_iterative(int* vec, int size) {

2: int n = pow((double)2, (double)size);

3: vector<int> currentSubset;

4: for (int i = 0; i < n; i++) {

` 5: currentSubset.clear();`

6: for (int j = 0; j < size; j++)

7: if (((i >> j) & 1) != 0)

` 8: currentSubset.push_back(vec[j]);`

9: if (currentSubset.empty())

10: cout << "empty set";

11: for (int i = 0; i < currentSubset.size(); i++)

12: cout << currentSubset.at(i) << " ";

` 13: cout << endl;`

` 14: }`

` 15: }`

no entiendo nada....

ReplyDeleteyo quiero saber el número de subconjuntos de el conjunto A={x pertenece a números naturales / 4<x a la potencia 2<144}

osea A={x pertenece a números naturales/2<x<12}

porfa dime la respuesta!!!!

ES IMPORTANTE!!!!!!!!!!

I don't understand anything

ReplyDeleteMinor improvement in your second piece of code:

ReplyDelete1. you can use i from 1 to n, because when i=0, there is no chance that something to be printed

2. you use i inside the loop i. Should use another variable instead.

Potong Pasir MRT at the doorstep, residents can easily access almost

ReplyDeleteto any destination through.the interlace condo

Fuck off !!

Delete