leetcode 330. Patching Array-蒲公英云

leetcode 330. 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:
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.

#include "stdafx.h"
#include<vector>
#include<set>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
class Solution {
public:
    set<set<int>>solu;
    void select(set<int>&selected, vector<int>&remain, int toselect)
    {
        if (selected.size() == toselect)
        {
            if (solu.find(selected) == solu.end())
            {
                solu.insert(selected);
            }
            return;
        }
        for (int i = 0; i < remain.size(); i++)
        {
            vector<int> re = remain;
            set<int>se = selected;
            se.insert(re[i]);
            re.erase(re.begin() + i);
            select(se, re, toselect);
        }
    }
    void Combination(int len, int toselect)//组合  
    {
        solu.clear();
        vector<int>remain;
        set<int>selected;
        for (int i = 1; i <= len; i++)
            remain.push_back(i);
        select(selected, remain, toselect);
        cout << "共有" << solu.size() << "种组合" << endl;
    }
    int minPatches(vector<int>& nums, int n) {
        set<int>mynum, allnums,re;
        vector<int>toinsert;
        for (int i = 1; i <= n; i++)
            allnums.insert(i);
        while (true)
        {
            for (int i = 1; i <= nums.size(); i++)
            {
                Combination(nums.size(), i);
                for (set<set<int>>::iterator it = solu.begin(); it != solu.end(); it++)
                {
                    int sum = 0;
                    for (set<int>::iterator iter = it->begin(); iter != it->end(); iter++)
                    {
                        sum += nums[*iter - 1];
                    }
                    mynum.insert(sum);
                }
            }
            re.clear();
            set_difference(allnums.begin(), allnums.end(), mynum.begin(), mynum.end(), inserter(re, re.begin()));
            if (re.empty())
                return toinsert.size();
            nums.push_back(*re.begin());
            toinsert.push_back(*re.begin());
            mynum.clear();    
        }
    }
};
int _tmain(int argc, _TCHAR* argv[])
{
    vector<int>nums;
    nums.push_back(1);
    nums.push_back(3);
    //nums.push_back(10);
    Solution sl;
    cout<<sl.minPatches(nums, 6);
    //.Combination(100,40);
    system("pause");
    return 0;
}