Постановка задачи
Нам дан набор целых чисел, и мы должны найти все возможные подмножества этого набора целых чисел. В следующем примере это более подробно рассматривается.
Подсказка
- Угадайте количество подмножеств для набора размером ‘n’
- Комбинации
Попробуйте сами
- C ++
- путь> C ++
- C ++
- Java
- Java
- h> Python
- Python
- JavaScript
- JavaScript
- Ruby
- Ruby
void get_all_subsets (vector & v, vector > & sets) {//ЗАДАЧИ: Запись - Ваш - Код}
Решение
- C ++
- C ++
- C ++
- Java
- Java
- Python
- Python
- JavaScript
- путь> JavaScript
- Ruby
- Ruby
int get_bit (int num, int bit) {int temp = (1 & v, vector > & sets) {int substs_count = pow ((double) 2, (двойной) v. size ()); for (int i = 0; i set; for (int j = 0; j v (myints, myints + sizeof (myints)/sizeof (int)); vector > подмножества; get_all_subsets (v, подмножества); cout :: итератор it = подмножества [i] .begin (); it! = подмножества [i] .end (); ++ it) {cout
Объяснение решения
Сложность времени выполнения
Экспоненциальная, O ( 2 n ∗ n ) O (2 ^ {n} * n) O (2 n ∗ n) — где ‘n’ — количество целых чисел в данном наборе.
Сложность памяти
Экспоненциальная, O ( 2 n ∗ n ) O ( 2 ^ {n} * n) O (2 n ∗ n)
Анализ решения
Есть несколько способов решить эту проблему. Обсудим тот, который проще и понятнее. Мы знаем, что для набора n элементов существует 2 n 2 ^ {n} 2 n подмножеств. Например, набор из 3 элементов будет иметь 8 подмножеств. Вот алгоритм, который мы будем использовать:
n = размер заданного целого числа setsubsets_count = 2 ^ nfor i = 0 в subsset_count формирует подмножество с использованием значения 'i' следующим образом : биты в номере 'i' представляют собой индекс элементов для выбора из исходного набора, если конкретный бит равен 1, выберите это число из исходного набора и добавьте его в текущее подмножество, например если i = 6, то есть 110 в двоичном формате, означает, что необходимо выбрать 1-й и 2-й элементы в исходном массиве. добавить текущее подмножество в список всех подмножеств
Обратите внимание, что порядок битов для выбора целых чисел из набора не имеет значения; выбор целых чисел слева направо приведет к тому же результату, что и выбор целых чисел справа налево.
