1982. Find Array Given Subset Sums LeetCode Solution

Last updated: February 25, 2025

In this guide, you will get 1982. Find Array Given Subset Sums LeetCode Solution with the best time and space complexity. The solution to Find Array Given Subset Sums problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find Array Given Subset Sums solution in C++
Find Array Given Subset Sums solution in Java
Find Array Given Subset Sums solution in Python
Additional Resources

1982. Find Array Given Subset Sums LeetCode Solution image

Problem Statement of Find Array Given Subset Sums

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 2n 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.

Example 1:

Input: n = 3, sums = [-3,-2,-1,0,0,1,2,3]
Output: [1,2,-3]
Explanation: [1,2,-3] is able to achieve the given subset sums:
– []: sum is 0
– [1]: sum is 1
– [2]: sum is 2
– [1,2]: sum is 3
– [-3]: sum is -3
– [1,-3]: sum is -2
– [2,-3]: sum is -1
– [1,2,-3]: sum is 0
Note that any permutation of [1,2,-3] and also any permutation of [-1,-2,3] will also be accepted.

Example 2:

Input: n = 2, sums = [0,0,0,0]
Output: [0,0]
Explanation: The only correct answer is [0,0].

Example 3:

Input: n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
Output: [0,-1,4,5]
Explanation: [0,-1,4,5] is able to achieve the given subset sums.

Constraints:

1 <= n <= 15
sums.length == 2n
-104 <= sums[i] <= 104

Complexity Analysis

Time Complexity: O(n \cdot 2^n)
Space Complexity: O(2^n)

1982. Find Array Given Subset Sums LeetCode Solution in C++

class Solution {
 public:
  vector<int> recoverArray(int n, vector<int>& sums) {
    ranges::sort(sums);
    return recover(sums);
  }

 private:
  vector<int> recover(const vector<int>& sums) {
    if (sums.size() == 1)  // sums[0] must be 0.
      return {};

    // Either num or -num must be in the final array.
    //  num + sumsExcludingNum = sumsIncludingNum
    // -num + sumsIncludingNum = sumsExcludingNum
    unordered_map<int, int> count;
    for (const int sum : sums)
      ++count[sum];

    const int num = sums[1] - sums[0];
    vector<int> sumsExcludingNum;
    vector<int> sumsIncludingNum;
    bool chooseSumsIncludingNum = false;

    for (const int sum : sums) {
      if (count[sum] == 0)
        continue;
      --count[sum];
      --count[sum + num];
      sumsExcludingNum.push_back(sum);
      sumsIncludingNum.push_back(sum + num);
      if (sum + num == 0)
        chooseSumsIncludingNum = true;
    }

    // Choose `sumsExludingNum` by default since we want to gradually strip
    // `num` from each sum in `sums` to have the final array. However, we should
    // always choose the group of sums with 0 since it's a must-have.
    vector<int> recovered =
        recover(chooseSumsIncludingNum ? sumsIncludingNum : sumsExcludingNum);
    recovered.push_back(chooseSumsIncludingNum ? -num : num);
    return recovered;
  }
};
/* code provided by PROGIEZ */

1982. Find Array Given Subset Sums LeetCode Solution in Java

class Solution {
  public int[] recoverArray(int n, int[] sums) {
    Arrays.sort(sums);
    return recover(sums).stream().mapToInt(Integer::intValue).toArray();
  }

  private List<Integer> recover(int[] sums) {
    if (sums.length == 1) // sums[0] must be 0.
      return new ArrayList<>();

    Map<Integer, Long> count = Arrays.stream(sums).boxed().collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    // Either num or -num must be in the final array.
    //  num + sumsExcludingNum = sumsIncludingNum
    // -num + sumsIncludingNum = sumsExcludingNum
    final int num = sums[1] - sums[0];
    int i = 0; // sumsExcludingNum/sumsIncludingNum's index
    int[] sumsExcludingNum = new int[sums.length / 2];
    int[] sumsIncludingNum = new int[sums.length / 2];
    boolean chooseSumsIncludingNum = false;

    for (final int sum : sums) {
      if (count.get(sum) == 0)
        continue;
      count.merge(sum, -1L, Long::sum);
      count.merge(sum + num, -1L, Long::sum);
      sumsExcludingNum[i] = sum;
      sumsIncludingNum[i] = sum + num;
      ++i;
      if (sum + num == 0)
        chooseSumsIncludingNum = true;
    }

    // Choose `sumsExludingNum` by default since we want to gradually strip
    // `num` from each sum in `sums` to have the final array. However, we should
    // always choose the group of sums with 0 since it's a must-have.
    List<Integer> recovered = recover(chooseSumsIncludingNum ? sumsIncludingNum : sumsExcludingNum);
    recovered.add(chooseSumsIncludingNum ? -num : num);
    return recovered;
  }
}
// code provided by PROGIEZ

1982. Find Array Given Subset Sums LeetCode Solution in Python

class Solution:
  def recoverArray(self, n: int, sums: list[int]) -> list[int]:
    def recover(sums: list[int]) -> list[int]:
      if len(sums) == 1:
        return []

      count = collections.Counter(sums)
      # Either num or -num must be in the final array.
      #  num + sumsExcludingNum = sumsIncludingNum
      # -num + sumsIncludingNum = sumsExcludingNum
      num = sums[1] - sums[0]
      sumsExcludingNum = []
      sumsIncludingNum = []
      chooseSumsExcludingNum = True

      for summ in sums:
        if count[summ] == 0:
          continue
        count[summ] -= 1
        count[summ + num] -= 1
        sumsExcludingNum.append(summ)
        sumsIncludingNum.append(summ + num)
        if summ + num == 0:
          chooseSumsExcludingNum = False

      # Choose `sumsExludingNum` by default since we want to gradually strip
      # `num` from each sum in `sums` to have the final array. However, we should
      # always choose the group of sums with 0 since it's a must-have.
      return ([num] + recover(sumsExcludingNum) if chooseSumsExcludingNum else
              [-num] + recover(sumsIncludingNum))

    return recover(sorted(sums))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents