部分集合の列挙

• $S, T \subseteq \{0,1.\ldots n\}, T \subseteq S$ を満たす $(S,T)$ の組は $3^n$ 通りある

  • 導出

• 計算量 $O(3^N)$ で全列挙できる

• (x - 1) & s を繰り返すことで全列挙できる

• Rust のコード

  std::iter::successors(Some(s), |x| {
      if *x == 0 {
          None
      } else {
          Some((x - 1) & s)
      }
  })
  

• 出題例: ABC332 E - Lucky bag

• 参考: ABC213 G の解説