Problem Statement
Explain how bit masking can be used to generate all subsets of a set of size n, and show time complexity.
Explanation
Each subset corresponds to a bit‐mask from 0 to (1<<n)−1. For mask in [0..2ⁿ−1], iterate bits from 0..n-1 and include element i if bit i in mask is set. This generates all 2ⁿ subsets in O(n·2ⁿ) time and O(n·2ⁿ) space for storing them or O(1) extra if streaming. Useful in small n search/backtracking and when bit operations are fast.
Code Solution
SolutionRead Only
for(int mask=0; mask<(1<<n); mask++){ List<int> subset=new ArrayList<>(); for(int i=0;i<n;i++){ if((mask & (1<<i))!=0) subset.add(arr[i]); } // process subset }