leetcode 330. Patching Array

- 日理万妓 2022-08-20 10:26 23阅读 0赞

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;
    }