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

// 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);

}