5853. Find Array Given Subset Sums

Description

image-20210822225103422

image-20210822225113726

Solution

Firstly, let’s think about a easier question—If sums‘s elements are all positive, how would you solve this?

  • Obviously, the minimum one m is the front one in the ans array.
  • How to find the next answers?
    • Delete all subset in sums from ans array, which should be $2^{ans.size()-1}$ elements to be deleted
    • How to do this in programming?
      • In each iteration, use a mask to mark the combination of ans‘s numbers, note that we just need to delete the combination of new found number and other’s
      • Use multiset

Then how to apply this to this problem? We can add up a positive number to convert the array into with all positive one. Especially, we add the number of -(sum of all negative number) . Then we apply the algorithm described above into new one, then we could get a temp ans array.

  • How to convert the ans into what we want?
    • We notice that after round up, sums array always starts with 0, then the next value is the largest negative value (Because the next value should be like (a + b + c - a- b- c -d), d is exactly the largest negative value)
    • So in the ans array, if we could find a serial of numbers which sum up to m, which means we could negate them them to make whole array sum up to 0. Then we negate them.

Code

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
class Solution {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        sort(sums.begin(), sums.end());
        int front = -sums[0];
        multiset<int> st;
        for(auto sum : sums){
            st.insert(sum + front);
        }
        st.erase(st.begin());
        vector<int> ans;
        ans.push_back(*st.begin());
        for(int i = 1; i < n; i++){
            for(int mask = 1; mask < (1<<i); mask++){
                if((mask >> (i-1)) & 1){
                    int sm = 0;
                    for(int j = 0; j < ans.size(); j++)
                        if(mask >> j & 1)
                            sm += ans[j];
                    st.erase(st.find(sm));
                }
            }
            ans.push_back(*st.begin());
        }

        for (int i = 0; i < (1 << n); i++) {
            int sm = 0;
            for (int j = 0; j < n; j++) if (i >> j & 1) sm += ans[j];
            if (sm == front) {
                for (int j = 0; j < n; j++) if (i >> j & 1) ans[j] = -ans[j];
                break;
            }
        }
        return ans;
    }
};