LeetCode 2044. 统计按位或能得到最大值的子集数目

题目链接：

力扣https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets/

 【分析】看数据量只有16，而且这属于从数组遍历过来一个元素要么有，要么没有的情况，也就是说可以用0，1来表示状态，那么很自然地就相当回溯了。

class Solution {
    int n, target;
    int ans = 0;
    public void backTrack(int t, int sum, int[] nums){
        if(t == n) {
            if (sum == target) ans++;
        }
        else{
            backTrack(t + 1, sum | nums[t], nums);
            backTrack(t + 1, sum, nums);
        }
    }
    public int countMaxOrSubsets(int[] nums) {

        n = nums.length;
        target = nums[0];
        for(int i = 1; i < n; i++){
            target |= nums[i];
        }
        backTrack(0, 0, nums);
        System.out.println(ans);
        return ans;
    }
}

class Solution {
    int n, target;
    int ans = 0;
    int[] nums;
    public void backTrack(int t, int sum){
        if(t == n) {
            if (sum == target) ans++;
        }
        else{
            backTrack(t + 1, sum | nums[t]);
            backTrack(t + 1, sum);
        }
    }

    public int countMaxOrSubsets(int[] nums) {

        n = nums.length;
        target = nums[0];
        this.nums = nums;
        for(int i = 1; i < n; i++){
            target |= nums[i];
        }
        backTrack(0, 0);
        System.out.println(ans);
        return ans;
    }
}