Partition Array into Two Equal Product Subsets

Partition Array into Two Equal Product Subsets - Problem

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.

Input & Output

Example 1 — Valid Partition

$ Input: nums = [2,3,6], target = 6

› Output: true

💡 Note: We can partition into {2,3} and {6}. Product of {2,3} = 2×3 = 6, Product of {6} = 6. Both equal target.

Example 2 — No Valid Partition

$ Input: nums = [1,2,3], target = 4

› Output: false

💡 Note: Total product is 1×2×3 = 6, but we need both subsets to have product 4, requiring total product = 16. Impossible.

Example 3 — Single Element Match

$ Input: nums = [4,1], target = 4

› Output: true

💡 Note: Partition into {4} and {1}. But product of {1} = 1 ≠ 4, so this is actually false.

Constraints

2 ≤ nums.length ≤ 10
1 ≤ nums[i] ≤ 100
nums contains distinct integers
1 ≤ target ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,3,6] and target 6

Process

Try different partitions and calculate products

Output

Return true if valid partition exists

Key Takeaway

🎯 Key Insight: Both subsets must have product = target, so total product must equal target²

Asked in

G Google 15 a Amazon 12

The key insight is that if both subsets have product equal to target, then the total product must equal target². The optimal approach uses bit manipulation to enumerate all possible subsets systematically. Time: O(n × 2^n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^n)	O(n)	Try all possible ways to partition the array using recursion
Bit Manipulation Enumeration	O(n × 2^n)	O(1)	Use bitmasks to enumerate all possible subsets efficiently

Recursive Backtracking — Algorithm Steps

Start with empty subsets
For each element, try adding to subset1 or subset2
Check if both subsets have product = target

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Empty subsets, try first element

Recurse

For each element, try both subsets

Check

Verify both products equal target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int* nums, int numsSize, int idx, long long prod1, long long prod2, int count1, int count2, int target) {
    if (idx == numsSize) {
        return count1 > 0 && count2 > 0 && prod1 == target && prod2 == target;
    }
    
    // Try adding nums[idx] to subset1
    if (backtrack(nums, numsSize, idx + 1, prod1 * nums[idx], prod2, count1 + 1, count2, target)) {
        return true;
    }
    
    // Try adding nums[idx] to subset2
    if (backtrack(nums, numsSize, idx + 1, prod1, prod2 * nums[idx], count1, count2 + 1, target)) {
        return true;
    }
    
    return false;
}

bool solution(int* nums, int numsSize, int target) {
    return backtrack(nums, numsSize, 0, 1, 1, 0, 0, target);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int target;
    scanf("%d", &target);
    
    bool result = solution(nums, numsSize, target);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each element has 2 choices (subset1 or subset2), leading to 2^n combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth is at most n levels deep

⚡ Linearithmic Space

21.3K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler