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