> https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets/solution/by-tong-zhu-mmeu/
思路1:不优化的回溯(穷举)
对于nums
的每个位置而言,都有两种状态,就是“选”或者“不选”,那么假设有位,就应当有种选择方案,如果方案符合条件,就将其放入子集方案中,否则不放入。
对于回溯的树来讲,就是一颗二叉树,每个非叶子节点有两个分支,分别代表“选择”和“不选择”,第i
层的节点,就是nums[i]
,这样就可以通过dfs树来遍历。
脑子里面要有下面这张图
代码1:
class Solution {
public:
void dfs(int& count_subs, vector<int>& nums, int cur_depth, int num_size, int cur_or, int max_or) {
if (cur_depth == num_size) {
if (max_or == cur_or) {
count_subs++;
}
return;
}
// 选择当前节点,也就是树的左分支
dfs(count_subs, nums, cur_depth + 1, num_size, cur_or | nums[cur_depth], max_or);
// 不选择当前节点,也就是树的右分支
dfs(count_subs, nums, cur_depth + 1, num_size, cur_or , max_or);
}
int countMaxOrSubsets(vector<int>& nums) {
int count_subs = 0;
int max_or = 0;
for (int num : nums) {
max_or |= num;
}
dfs(count_subs, nums, 0, nums.size(), 0, max_or);
return count_subs;
}
};
思路2:回溯穷举(带剪枝)
可以对树进行剪枝。优化两点:1.树本身的结构不一样 2.加入了剪枝<br /> 首先,可以**通过树的叶子节点一定是数组的最后一个元素**这样的办法,来简化树的形状。<br /> 然后,统计最大的按位或的结果,也就是所有元素全部或一遍。得到`max_or`。<br /> 接着,遍历简化之后的那棵树,如果当前的按位或结果`cur_or`和`max_or`相等,那么,就说明剩下的所有元素都是可有可无的。剩下的元素一共`num_size - cur_depth`个,那么,对应的`cur_depth`下,一共应该有![](https://g.yuque.com/gr/latex?2%5E%7Bnum%5C_size-cur%5C_depth%7D#card=math&code=2%5E%7Bnum%5C_size-cur%5C_depth%7D&id=PyT4z)个子集。否则,就继续DFS遍历这棵树。<br />“以数组的最后一个数字作为叶子节点”和“二叉是否选择当前节点”的两棵树之间的异同:<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/1626815/1647335078269-600f141e-02db-4d6a-aaea-b672546e92ae.png#clientId=u90e4aa07-2758-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=582&id=ubbc21a0f&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1280&originWidth=1211&originalType=binary&ratio=1&rotation=0&showTitle=false&size=960959&status=done&style=none&taskId=ucd5828c4-b002-4810-bed4-8c5061bea1d&title=&width=550.4545335237648)<br />然后加上剪枝条件,提前返回就可以得到最优化的方案了。(两棵树本质上就是一棵树的两种呈现形式)
代码2:
class Solution {
public:
int count_subs = 0;
void dfs(vector<int>& nums, int cur_depth, int cur_or, int max_or) {
int num_size = nums.size();
if (cur_or == max_or) {
count_subs += (1 << (num_size - cur_depth));
return;
}
for (int i = cur_depth; i < num_size; ++i) {
dfs(nums, i + 1, cur_or | nums[i], max_or);
}
}
int countMaxOrSubsets(vector<int>& nums) {
int max_or = 0;
for (int num : nums) {
max_or |= num;
}
dfs(nums, 0, 0, max_or);
return count_subs;
}
};