回溯、数组-[5904] 统计按位或能得到最大值的子集数目

回溯、数组-[5904] 统计按位或能得到最大值的子集数目

 * 类比例子

    假如nums=[2,2,4], 则nums有多少个子集
    其实示例2已经给我们暗示了。如果包括空子集则，则一个集合中它的子集个数为 2^(集合中元素个数)，
    由于题目中说了排除空子集所以对于那个例子需要-1；这也说明了有一个优化的方向，如果数组有序，或者元素全部相同，其实可以优化计算，这里就不说这些了，如果有利用这个做的小伙伴希望分享一下；另外就是相同的元素位置不同视为不同的元素，这其实是一个关键点，有没有这个条件，结果是不一样的，一般来说当忽略相同元素时，我们会先对数组排序，在首次出现某个重复元素时，让它被计算一次，下一次直接跳过这些相同的元素；
接下来我们看看这里nums的子集都有哪些:
    []      // 空集

    [2]     // 第一个2
    [2,2]   // 第一个2,第二个2
    [2,2,4] // 第一个2,第二个2
    [2,4]   // 第一个2

    [2]     // 第二个2
    [2,4]   // 第二个2

    [4]
以上是nums的8个子集

* 具体解法

    假如nums=[2,2,4], 则最大值为4，我们可先把它的所有子集列出来
    （和上面一样，不过这里简化了一下，注意之后的代码执行顺序基本像下面这样，除了空集哈, 另外c1表示列数）
    c1  c2  c3
    []
    [2]
        [2]      
            [4]
        [4]
    [2]
        [4]
    [4]

    col1: 表示遍历所有元素，每个可能子集的第一个元素
    col2: 表示子集中第一个元素确定后，子集中的第二个元素
    col3: 表示子集中第一、第二个元素确定后，子集中的第三个元素
 

 * 注意事项

> 这个题主要使用回溯解法主要注意2个点：
> 1.位置不同元素值相同的元素视为两种元素；
> 2.注意每次回溯是否缩小区间，是否有结束条件；

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;
        for(int i = 0; i < nums.length; i++)
            max |= nums[i];

        int[] ans = new int[1];

        // 遍历所有元素，并且将nums[i]当做子集的第一个元素
        for(int i = 0; i < nums.length; i++){
            backtrace(i + 1, nums[i], nums, max, ans);
        }

        return ans[0];
    }

    
    private void backtrace(int i, int val, int[] nums, int max, int[] ans){
        if(max == val)
            ans[0]++;

        for(; i < nums.length; i++){
            backtrace(i + 1, val | nums[i], nums, max, ans);
        }          

        return; 
    }
}