A non-recursive trick for subsets generation II

This problem requires finding out all the subsets of a small set S. For each subset S', you need to determine whether:

Product(S') == Product(S - S') == Target

Hence you need to find all S'. Subsets generation trick, as explained before on post I with the same title, does the trick here for an exponential-time solution, but since |S| is small (12), it works just fine. Bonus points for early termination whenever we reach a dead end. Code is down below, cheers, ACC.

Partition Array into Two Equal Product Subsets - LeetCode

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.

 

Example 1:

Input: nums = [3,1,6,8,4], target = 24

Output: true

Explanation: The subsets [3, 8] and [1, 6, 4] each have a product of 24. Hence, the output is true.

Example 2:

Input: nums = [2,5,3,7], target = 15

Output: false

Explanation: There is no way to partition nums into two non-empty disjoint subsets such that both subsets have a product of 15. Hence, the output is false.

 

Constraints:

• 3 <= nums.length <= 12
• 1 <= target <= 1015
• 1 <= nums[i] <= 100
• All elements of nums are distinct.

public bool CheckEqualPartitions(int[] nums, long target)
{
    int numberSubsets = (int)Math.Pow(2, nums.Length);

    for (int i = 0; i < numberSubsets; i++)
    {
        long prodOne = 1;
        long prodZero = 1;

        int temp = i;
        for (int j = nums.Length - 1; j >= 0; j--)
        {
            if (temp % 2 == 1) prodOne *= nums[j];
            else prodZero *= nums[j];
            temp /= 2;

            if (prodOne > target ||
                prodZero > target ||
                ((prodOne == 0 || prodZero == 0) && target > 0)) break;
        }

        if (prodOne == target && prodZero == target) return true;
    }
    return false;
}