Find Array Given Subset Sums - Practice Coding Problems

Find Array Given Subset Sums - Problem

You are given an integer n representing the length of an unknown array that you are trying to recover. You are also given an array sums containing the values of all 2^n subset sums of the unknown array (in no particular order).

Return the array ans of length n representing the unknown array. If multiple answers exist, return any of them.

An array sub is a subset of an array arr if sub can be obtained from arr by deleting some (possibly zero or all) elements of arr. The sum of the elements in sub is one possible subset sum of arr. The sum of an empty array is considered to be 0.

Note: Test cases are generated such that there will always be at least one correct answer.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, sums = [-3,-2,-1,0,0,1,2,3]

› Output: [1,2,-3]

💡 Note: The array [1,2,-3] generates subset sums: [] = 0, [1] = 1, [2] = 2, [-3] = -3, [1,2] = 3, [1,-3] = -2, [2,-3] = -1, [1,2,-3] = 0. When sorted: [-3,-2,-1,0,0,1,2,3]

Example 2 — Small Array

$ Input: n = 2, sums = [0,0,0,0]

› Output: [0,0]

💡 Note: The array [0,0] generates all zero subset sums: [] = 0, [0] = 0, [0] = 0, [0,0] = 0

Example 3 — Single Element

$ Input: n = 1, sums = [0,5]

› Output: [5]

💡 Note: The array [5] generates subset sums: [] = 0, [5] = 5

Constraints

1 ≤ n ≤ 15
sums.length == 2ⁿ
-10⁴ ≤ sums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

n=3, sums=[-3,-2,-1,0,0,1,2,3] (all 2^3=8 subset sums)

Process

Split sums into groups and identify elements recursively

Output

Original array [1,2,-3] that generates these sums

Key Takeaway

🎯 Key Insight: Split subset sums by element inclusion to reveal individual values

Asked in

G Google 15 f Facebook 12 a Amazon 8

The divide and conquer approach is optimal. Split subset sums into groups based on including/excluding elements. The key insight is that corresponding sums differ by the element value. Best approach uses recursive splitting: Time: O(n × 2^n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Backtracking	O(2^n × 2^n)	O(2^n)	Try all possible arrays and check if they generate the given subset sums
Divide and Conquer	O(n × 2^n)	O(2^n)	Recursively split sums into two groups based on including/excluding elements

Brute Force Backtracking — Algorithm Steps

Generate all possible arrays of length n
For each array, compute all 2^n subset sums
Check if the computed sums match the given sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Candidates

Create all possible arrays of length n

Compute Subset Sums

For each candidate, calculate all 2^n subset sums

Verify Match

Check if computed sums match given sums

Code -

solution.c — C

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

int* solution(int n, int* sums, int sumsSize) {
    int* result = (int*)calloc(n, sizeof(int));
    
    if (n == 1) {
        for (int i = 0; i < sumsSize; i++) {
            if (sums[i] != 0) {
                result[0] = sums[i];
                break;
            }
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for array
    int sums[1000];
    int sumsSize = 0;
    
    char* token = strtok(line + 1, ",]"); // skip '['
    while (token != NULL) {
        sums[sumsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int* result = solution(n, sums, sumsSize);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × 2^n)

Try 2^n possible arrays, each requiring 2^n subset sum computations

⚠ Quadratic Growth

Space Complexity

O(2^n)

Store subset sums for verification

⚠ Quadratic Space

23.4K Views

Medium Frequency

~45 min Avg. Time

876 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

Brute Force Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler