İçeriğe geç

Bit maskesiyle her alt küme

Kolay#bitmask#subsets~20 dk

Görev tanımı

Problem

Birbirinden farklı öğelerden oluşan bir liste verildiğinde, onun her alt kümesini döndür. Alt kümeleri sayarak sırala: bir alt kümeyi, items[i] dahilse i. biti 1 olan bir ikili sayı olarak oku ve alt kümeleri bu sayı 0'dan en büyüğe kadar listele. Her alt kümenin içinde öğeleri orijinal sıralarında tut. Listede en fazla 15 öğe var; boş listenin de bir alt kümesi var.

Örnekler

Input:  items = ["a", "b"]
Output: [[], ['a'], ['b'], ['a', 'b']]
Neden: 0, 1, 2 ve 3 sayıları ikili olarak 00, 01, 10 ve 11
Input:  items = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Neden: items[2], 2. bit yandığında 4 sayısından itibaren katılır
Input:  items = []
Output: [[]]
Neden: edge case: boş küme tek alt kümedir

İpuçları

0 / 3

Hedef zaman
O(n · 2ⁿ)
Hedef alan
O(n · 2ⁿ)

Kısıtlar

  • items are distinct
  • 0 ≤ items.length ≤ 15

Kodda değil de fikirde mi takıldın? Küme olarak bit maskesi bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case