3566. Partition Array into Two Equal Product Subsets

You are given an integer array nums containing distinct positive integers and an integer target.

Determine if you can partition nums into two non-empty disjoint subsets, with each element belonging to exactly one subset, such that the product of the elements in each subset is equal to target.

Return true if such a partition exists and false otherwise.

A subset of an array is a selection of elements of the array.

class Solution {
public:
    bool checkEqualPartitions(vector<int>& nums, long long target) {
        int n = nums.size();
        vector<bool> masks(1<<n);
        auto ok = [&](int mask) {
            long long mul = 1;
            for(int i = 0; i < n and mul <= target; i++) if((mask>>i)&1) mul *= nums[i];
            return mul == target;
        };
        for(int mask = 1; mask < 1<<n; mask++) {
            masks[mask] = ok(mask);
            if(masks[mask]) continue;
            for(int base = mask, sub = base; sub and !masks[mask]; sub = (sub - 1) & mask) {
                if(masks[sub] and masks[mask ^ sub]) masks[mask] = true;
            }
        }
        return masks.back();
    }
};