leetcode 216. Combination Sum III

深碍√TFBOYSˉ_ 2022-08-21 04:49 28阅读 0赞

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

尼玛，不知道题目为什么要限制只能用1-9，表示不理解。开始按找全部组合做的，按题目要求过滤一下就行。

class Solution {
    	void do_once(int k,int n, map<set<int>, int>&candi)
    	{
    		map<set<int>, int>newcandi;
    		for (map<set<int>, int>::iterator it = candi.begin(); it != candi.end(); it++)
    		{
    			if (k == 1)
    			{
    				if (n - it->second > 0 && it->first.find(n - it->second) == it->first.end())
    				{
    					set<int>nums = it->first;
    					nums.insert(n - it->second);
    					newcandi[nums] = n;
    				}
    			}
    			else
    			for (int i = 1; i <= n - it->second-k+1; i++)
    			{
    				 if (it->second+i<=n&&it->first.find(i) == it->first.end())
    				{
    					set<int>nums = it->first;
    					nums.insert(i);
    					newcandi[nums] = it->second +i;
    				}
    			}
    		}
    		candi = newcandi;
    	}
    public:
    	vector<vector<int>> combinationSum3(int k, int n) {
    		vector<vector<int>>re;
    		map<set<int>,int>candi;
    		set<int>aa;
    		candi[aa] = 0;
    		while (k>0)
    		{
    			do_once(k,n, candi);
    			k--;
    		}
    		for (map<set<int>, int>::iterator it = candi.begin(); it != candi.end(); it++)
    			if (it->second == n)
    				re.push_back(vector<int>(it->first.begin(), it->first.end()));
    		return re;
    	}
    };

这个太慢，不能满意

class Solution {
    	int sum(vector<int>nums, int startpos, int endpos)
    	{
    		int re = 0;
    		for (int j = startpos; j <= endpos; j++)
    			re += nums[j];
    		return re;
    	}
    public:
    	vector<vector<int>> combinationSum3(int k, int n) {
    		vector<vector<int>>re;
    		if (k == 0)
    			return re;
    		if (k == 1)
    		{
    			vector<int>aa;
    			aa.push_back(n);
    			if (n <= 9)
    				re.push_back(aa);
    			return re;
    		}
    		vector<int>nums(k);
    		for (int i = 0; i < k - 1; i++)
    			nums[i] = i + 1;
    		int index = k - 1;
    		while (index >= 1)
    		{
    			int jj = index;
    			while (jj != k - 1)
    			{
    				nums[jj] = nums[jj - 1] + 1;
    				jj++;
    			}
    			nums[k - 1] = n - sum(nums, 0, k - 2);
    			while (nums[k - 1] > nums[k - 2])
    			{
    				bool flag = true;
    				for (int i = k - 1; i >= 0; i--)
    					if (nums[i] > 9)
    					{
    						flag = false;
    						break;
    					}
    				if (flag)
    					re.push_back(nums);
    				nums[k - 1]--;
    				nums[k - 2]++;
    			}
    			int pp = 3;
    			while (k - pp >= 0)
    			{
    				nums[k - pp]++;
    				if (nums[k - pp] * pp + pp*(pp - 1) / 2 <= n - sum(nums, 0, k - pp - 1))
    				{
    					index = k - pp + 1;
    					break;
    				}
    				else
    					pp++;
    			}
    			if (k - pp < 0)
    				break;
    		}
    		return re;
    	}
    };

accepted