题目描述
2044. 统计按位或能得到最大值的子集数目
解法：DFS
二进制枚举和状态压缩的 DP 我硬是没看懂什么意思，但是 DFS 还是很明确的，对于一个数，取或者不取其是两条分支，按照前面数取后面数的规则，我们保证了将多条「具有相同前缀」的搜索路径进行复用，从而不用担心子集枚举不全的问题
class Solution {
public:int countMaxOrSubsets(vector<int>& nums) {
int ans = 0, max = 0;dfs(0, 0, max, ans, nums);return ans;}void dfs(int u, int val, int& max, int& ans, vector<int>& nums){
if (u == nums.size()){
if (val > max){
max = val;ans = 1;}else if (val == max)ans++;return;}dfs(u + 1, val, max, ans, nums);dfs(u + 1, val | nums[u], max, ans, nums);}
};