3566. 等积子集的划分方案

给你一个整数数组 nums，其中包含的正整数 互不相同 ，另给你一个整数 target。

请判断是否可以将 nums 分成两个 非空、互不相交 的 子集 ，并且每个元素必须 恰好 属于 一个 子集，使得这两个子集中元素的乘积都等于 target。

如果存在这样的划分，返回 true；否则，返回 false。

子集 是数组中元素的一个选择集合。

示例 1：

输入： nums = [3,1,6,8,4], target = 24

输出： true

**解释：**子集 [3, 8] 和 [1, 6, 4] 的乘积均为 24。因此，输出为 true 。

示例 2：

输入： nums = [2,5,3,7], target = 15

输出： false

**解释：**无法将 nums 划分为两个非空的互不相交子集，使得它们的乘积均为 15。因此，输出为 false。

提示：

  • 3 <= nums.length <= 12
  • 1 <= target <= 10^15
  • 1 <= nums[i] <= 100
  • nums 中的所有元素互不相同。

递归选哪个，求出一个，再算另一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;
        int[] vis = new int[n];
        if (dfs(-1, 1, nums, target, vis)) {
            long another = 1;
            for (int i = 0; i < n; i++) {
                if (vis[i] == 0) another *= nums[i];
            }
            return another == target;
        }
        else return false;
    }
    public boolean dfs(int i, long cur, int[] nums, long target, int[] vis) {
        if (cur == target) return true;
        int n = nums.length;
        for (int j = i+1; j < n; j++) {
            vis[j] = 1;
            if (dfs(j, cur*nums[j], nums, target, vis)) return true;
            vis[j] = 0;
        }
        return false;
    }

}

递归选不选，同时求两个子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;
        int[] vis = new int[n];
        if (dfs(-1, 1, nums, target, vis)) {
            long another = 1;
            for (int i = 0; i < n; i++) {
                if (vis[i] == 0) another *= nums[i];
            }
            return another == target;
        }
        else return false;
    }
    public boolean dfs(int i, long cur, int[] nums, long target, int[] vis) {
        if (cur == target) return true;
        int n = nums.length;
        for (int j = i+1; j < n; j++) {
            vis[j] = 1;
            if (dfs(j, cur*nums[j], nums, target, vis)) return true;
            vis[j] = 0;
        }
        return false;
    }

}

枚举所有选择情况的二进制子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;
        int u = 1 << n;
        for (int s = 1; s < u; s++) {
            long cur1 = 1, cur2 = 1;
            for (int i = 0; i < n; i++) {
                if ((s & (1 << i)) > 0) {
                    cur1 *= nums[i];
                } else {
                    cur2 *= nums[i];
                }
            }
            if (cur1 == target && cur2 == target) return true;
        }
        return false;
    }
}