leetcode 216. Combination Sum III Add to List (枚举子集,限定集合大小,和为定值)

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.

题意:1..9个数,从中选择k个,和为n,要求输出所有满足题意的集合。

思路:枚举子集,根据sum和集合元素个数剪枝即可。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月13日 星期四 15时44分56秒
 4File Name :216.cpp
 5************************************************ */
 6class Solution {
 7public:
 8    set<vector<int> >se;
 9    vector<vector<int> >res;
10    int B[1005];
11    void get_subset(int n,int *B,int cur,int cnt,int k,int sum,int tar)
12    {
13	if (cur==n)
14	{
15	    if (cnt!=k||sum!=tar) return;
16	    vector<int>tmp;
17	    for ( int i = 0 ; i < n ; i++)
18		if (B[i]) tmp.push_back(i+1);
19	    se.insert(tmp);
20	    return ;
21	}
22	if (cnt+1<=k&&sum+(cur+1)<=tar)
23	{
24	    B[cur] = 1;
25	    get_subset(n,B,cur+1,cnt+1,k,sum+(cur+1),tar);
26	}
27	B[cur] = 0 ;
28	get_subset(n,B,cur+1,cnt,k,sum,tar);
29    }
30    vector<vector<int>> combinationSum3(int k, int n) {
31	get_subset(9,B,0,0,k,0,n);
32	for ( auto &it : se) res.push_back(it);
33	return res;
34    }
35};