Description

Submission

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> num2idx(1000 + 2 * k + 1, -1);

        for (int i = 0; i < n; ++i) {
            num2idx[nums[i] + k] = i;
        }
        
        int ret = 0;
        for(int state = 0; state < (1 << n); ++state) {
            bool isGood = true;
            for (int i = 0; i < n; ++i) {
                if ((state>>i)&1) {
                    if(num2idx[nums[i] + 2*k] != -1 && (state>>num2idx[nums[i] + 2*k])&1) {
                        isGood = false;
                        break;
                    }
                    if(num2idx[nums[i]] != -1 && (state>>num2idx[nums[i]])&1) {
                        isGood = false;
                        break;
                    }
                }
            }
            ret += isGood && state;
        }

        return ret;
    }
};

DFS might be better, but the scale of the data fits in brute-force very well.