2044. Count Number of Maximum Bitwise-OR Subsets
Approach
Compute max OR of whole array; DFS enumerate subsets counting those achieving max OR.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
Backtracking explores all possible solutions by building candidates incrementally and abandoning ("pruning") branches that cannot lead to a valid result. It powers N-Queens, Sudoku solver, permutations, and subset generation. Prune early to reduce the effective search space.
// Approach: Compute max OR of whole array; DFS enumerate subsets counting those achieving max OR.
// Time: O(2^n) Space: O(n)
public class Solution
{
private int ans = 0;
public int CountMaxOrSubsets(int[] nums)
{
int ors = nums.Aggregate((a, b) => a | b);
Dfs(nums, 0, 0, ors);
return ans;
}
private void Dfs(int[] nums, int i, int path, int ors)
{
if (i == nums.Length)
{
if (path == ors)
++ans;
return;
}
Dfs(nums, i + 1, path, ors);
Dfs(nums, i + 1, path | nums[i], ors);
}
}