Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6
Output: 1 
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

Basic solution (Time limit exceeded)

class Solution {
public:
    
    vector<vector<int>> combsHelper(vector<int>&nums) {
        vector<vector<int>> ans;
        ans.push_back(vector<int>());
        for (auto num : nums) {
            int size = ans.size();
            int it = 0;
            while(it < size) {
                vector<int> tmp = ans[it];
                tmp.push_back(num);
                ans.push_back(tmp);
                it++;
            }
        }
        return ans;
    }
    
    int minPatches(vector<int>& nums, int n) {
        int ans = 0;
        vector<vector<int>> combs;
        set<int> done, remaining;
        if (n < 2) {
            return 0;
        }
        
        combs = combsHelper(nums);
        done = getDone(combs);
        remaining = getRemaining(done, n);
        
        while(!remaining.empty()) {
            set<int>::iterator it = remaining.begin();
            int num = *it;
            remaining.erase(it);
            UpdateCombs(combs, num);          
            done = getDone(combs);      
            remaining = getRemaining(done, n);
            ans++;
        }
        return ans;
    }
    
    void UpdateCombs(vector<vector<int>>& combs, int num) {
        vector<vector<int>> newCombs;
        for (auto comb : combs) {
            newCombs.push_back(comb);
            vector<int> tmp = comb;
            tmp.push_back(num);
            newCombs.push_back(tmp);
        }
        combs.swap(newCombs);
    }
    
    set<int> getDone(vector<vector<int>>& combs) {
        // Fill the existing coverage.
        set<int> done;
        for (auto comb : combs) {
            int sum = 0;
            for (int num : comb) {
                sum += num;
            }
            done.insert(sum);
        }
        return done;
    }

    set<int> getRemaining(set<int>& done, int n) {
        set<int> remaining;
        // Fill the remaining one.
        for (int i = 1; i <= n; i++) {
            if (done.count(i) == 0) {
                remaining.insert(i);
            }
        }
        return remaining;
    }
};

=======