# 330 Patching Arrays

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:

```
nums = [1, 3], n = 6
Return 1.
```

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:

```
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].
```

Example 3:

```
nums = [1, 2, 2], n = 5
Return 0.
```

//figure representing how my arrays work ![](http://i.imgur.com/WVS4pQ1.png)

```cpp
// Note to self: to optimize this, make and check all the comparisons at the beginning 
// rather than finding the patches, and checking them once over again.

// when you come back work on the combinations generator to produce all combinations
// algorithm is correct but not all possible combinations are produced.
// ex. in 1 5 10 2 4, you are missing possibility 1 10 2 because you assumed that 
// you need one dynamic counter when in fact you can have to num.size() amount...


#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

void print3d(vector<vector<vector<int>>> &nums) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.at(i).size(); j++) {
            for (int k = 0; k < nums.at(i).at(j).size(); k++) {
                cout << nums.at(i).at(j).at(k) << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }
}

void print1D(vector<int> &nums) {
    for (auto i : nums) cout << i << ' '; cout << endl;
}

inline vector<int> sum3D(vector<vector<vector<int>>> *nums) {
    vector<int> sum;
    for (int i = 0; i < (*nums).size(); i++) {
        for (int j = 0; j < (*nums).at(i).size(); j++) {
            sum.push_back(accumulate((*nums).at(i).at(j).begin(), (*nums).at(i).at(j).end(), 0));
        }
    }
    return sum;
}

bool confirmRange(vector<int> *sums, int n) {
    std::sort((*sums).begin(), (*sums).end());
    std::unique((*sums).begin(), (*sums).end());

    vector<int> comparisonVect;
    for (int i = 1; i <= n; i++) {
        comparisonVect.push_back(i);
    }

    //print1D(comparisonVect);
    //print1D((*sums));

    if ((*sums).size() < n) return false;

    // check if sums have range [1,n]
    for (int i = 0; i < n; i++) {
        if ((*sums).at(i) == comparisonVect.at(i)) continue;
        else return false;
    }
    return true;
}


/*
matrixSize: number of countable rows or columns in the square matrix + 1
*/
inline vector<vector<int>> combinationMatrix(vector<int> *nums, int matrixSize, 
    int numPushBacks, int numPushBackStart, int nextColumn) {
    vector<vector<int>> matrix;
    vector<int> temp;

    int numPushBackReset = numPushBackStart;

    for (int i = 0; i < matrixSize; i++) {
        for (int j = nextColumn; j < matrixSize; j++) {
            temp.push_back((*nums).at(i));

            for (int k = 0; k < numPushBacks; k++) {
                temp.push_back((*nums).at(numPushBackStart));
                numPushBackStart++;
            }
            numPushBackStart = numPushBackReset;
            temp.push_back((*nums).at(j));
            matrix.push_back(temp);
            temp.clear();
        }
        nextColumn++;
        numPushBackReset++;
        numPushBackStart = numPushBackReset;
    }

    return matrix;
}

int minPatches(vector<int>& nums, int n) {
    int numPatches = 0;
    vector<vector<vector <int>>> combinationMatricies;
    vector<int> sumArray;
    vector<vector<int>> temp2;
    vector<int> temp;

    // used at the end with to minimize the number of patches:
    vector<int> patches;
    vector<int> original = nums;
    vector<int> orginalCopy = nums;

    while (true) {
        std::sort(nums.begin(), nums.end());
        int matrixSize = nums.size();
        int matrixSizeChange = matrixSize;
        int numPushBacks = 0;
        int numPushBackStart = 1;
        int nextColumn = 1;

        temp.clear();
        temp2.clear();
        for (auto i : nums) {
            temp.push_back(i);
            temp2.push_back(temp);
            combinationMatricies.push_back(temp2);
            temp.clear();
            temp2.clear();
        }

        // insert all possible combinations for any nCk
        // -2 because we add two edge cases independently
        for (int i = 0; i < matrixSize - 2; i++) {
            combinationMatricies.push_back(combinationMatrix(&nums, matrixSizeChange, numPushBacks,
                numPushBackStart, nextColumn));
            numPushBacks++;
            nextColumn++;
        }

        for (auto i : nums) {
            temp.push_back(i);
        }
        temp2.push_back(temp);
        combinationMatricies.push_back(temp2);
        temp.clear();
        temp2.clear();

        //print3d(combinationMatricies);

        // sum all the elements in the vector
        vector<int> sum = sum3D(&combinationMatricies);
        //print1D(sum);
        //cout << endl;

        // success
        if (confirmRange(&sum, n)) {
            //return numPatches;
            break;
        }

        // add another patch. Doing brute force way
        else {
            // start from 1!
            std::sort(nums.begin(), nums.end());
            int patchCounter = 1;
            for (int i = 0; i < nums.size(); i++) {
                if (nums.at(i) == patchCounter) {
                    patchCounter++;
                }
                else {
                    // if we are here, then the range tested was incomplete
                    nums.push_back(patchCounter);
                    // actual numbers inserted into the original vector
                    patches.push_back(patchCounter);
                    numPatches++;
                    sumArray.clear();
                    combinationMatricies.clear();
                    break;
                }
            }
        }
    }

    // minimize the number of patches by finding the minimum number of patches (numbers added) 
    // that produce range required. Combinations will be returned in increasing vector size, so
    // it won't be nessessary to test them all.

    // 1) combination of the patches
    combinationMatricies.clear(); temp.clear(); temp2.clear();
    std::sort(patches.begin(), patches.end());

    //print1D(patches);
    //cout << endl << endl;

    int matrixSize = patches.size();
    int matrixSizeChange = matrixSize;
    int numPushBacks = 0;
    int numPushBackStart = 1;
    int nextColumn = 1;

    temp.clear();
    temp2.clear();
    for (auto i : patches) {
        temp.push_back(i);
        temp2.push_back(temp);
        combinationMatricies.push_back(temp2);
        temp.clear();
        temp2.clear();
    }

    for (int i = 0; i < matrixSize - 2; i++) {
        combinationMatricies.push_back(combinationMatrix(&patches, matrixSizeChange, numPushBacks,
            numPushBackStart, nextColumn));
        numPushBacks++;
        nextColumn++;
    }

    for (auto i : patches) {
        temp.push_back(i);
    }
    temp2.push_back(temp);
    combinationMatricies.push_back(temp2);

    // 2) Add each pair of combination patch into nums, and test whether or not it was successful
    vector<vector<vector<int>>> combinations_new;

    int sizePatch = 0;
    // now combinationMatricies is overwritten as the combination of patches
    for (int i = 0; i < combinationMatricies.size(); i++) {
        for (int j = 0; j < combinationMatricies.at(i).size(); j++) {
            for (int k = 0; k < combinationMatricies.at(i).at(j).size(); k++) {
                // add the pair
                original.push_back(combinationMatricies.at(i).at(j).at(k));
                cout << combinationMatricies.at(i).at(j).at(k) << ' ';
                sizePatch++;
            }
            cout << endl;
            // test the pair by finding all the new combinations made by the new pair

            std::sort(patches.begin(), patches.end());
            //print1D(patches);

            // find the sum of combinations made afer the pair combination was added.
            int matrixSize = original.size();
            int matrixSizeChange = matrixSize;
            int numPushBacks = 0;
            int numPushBackStart = 1;
            int nextColumn = 1;

            temp.clear();
            temp2.clear();
            for (auto i : original) {
                temp.push_back(i);
                temp2.push_back(temp);
                combinations_new.push_back(temp2);
                temp.clear();
                temp2.clear();
            }

            for (int i = 0; i < matrixSize - 2; i++) {
                combinations_new.push_back(combinationMatrix(&original, matrixSizeChange, numPushBacks,
                    numPushBackStart, nextColumn));
                numPushBacks++;
                nextColumn++;
            }

            for (auto i : original) {
                temp.push_back(i);
            }
            temp2.push_back(temp);
            combinations_new.push_back(temp2);

            cout << "3d print: "; print3d(combinations_new); cout << "_________" << endl;

            // sum all the elements in the vector
            vector<int> sum = sum3D(&combinations_new);
            std::sort(sum.begin(), sum.end());
            cout << endl << endl;
            print1D(sum);

            // success -> return the size of the patch
            if (confirmRange(&sum, n)) {
                return sizePatch;
            }

            // otherwise check the next patch, it's guareenteed to be one of them
            else {
                original = orginalCopy;
                combinations_new.clear();
                sizePatch = 0;
            }
        }
    }
}



int main()
{
    vector<int> test = { 1,5,10 };
    vector<int> test2 = { 1,3,4 };
    cout << minPatches(test, 20);

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/330_patching_arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.