Skip to content

1982. Find Array Given Subset Sums 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(2^n)$
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
  }
};

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
  }
}

 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
26
27
28
29
30
31
32
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))