# Combination

#Combination

> Given two integers n and k, return all possible combinations of k numbers out of 1,2,...,n.

[1,2], [1,3], [2,3]. 注意：[2,3]和[3,2]是相同的，我们只要求有其中一个就可以了.

```c++

class Solution {
public:
vector > combine(int n, int k) {
vector> ret;
if(n <= 0) //corner case invalid check
return ret;

vector curr;
DFS(ret,curr, n, k, 1); //we pass ret as reference at here
return ret;
}

void DFS(vector>& ret, vector curr, int n, int k, int level)
{
if(curr.size() == k)
{
ret.push_back(curr);
return;
}
if(curr.size() > k) // consider this check to save run time
return;

for(int i = level; i <= n; ++i)
{
curr.push_back(i);
DFS(ret,curr,n,k,i+1);
curr.pop_back();
}
}

};
```

# Combination Sum

> Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

> The same repeated number may be chosen from C unlimited number of times.

Note:
1. All numbers (including target) will be positive integers.
2. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
3. The solution set must not contain duplicate combinations.

1. 所有给定的数字均为正整数.(这意味着我们加corner case invalid check的时候要加一条，如果给定T不是正整数，我们就没必要在往下进行了)

2. 所有的答案组中要满足升序排列.

3. 最后的答案数组不能包含重复答案.

```c++
class Solution {
public:
vector > combinationSum(vector &candidates, int target) {
vector> ret;
//corner case invalid check
if(candidates.size() == 0 || target < 0)
return ret;
vector curr;
sort(candidates.begin(),candidates.end()); //because the requirments need the elements should be in non-descending order
BackTracking(ret,curr,candidates,target,0);
return ret;
}

/* we use reference at here because the function return type is 0, make the code understand easily */
void BackTracking(vector>& ret, vector curr, vector candidates, int target, int level)
{
if(target == 0)
{
ret.push_back(curr);
return;
}
else if(target < 0) //save time
return;

for(int i = level; i < candidates.size(); ++i)
{
target -= candidates[i];
curr.push_back(candidates[i]);
BackTracking(ret,curr,candidates,target,i); //unlike combination, we do not use i+1 because we can use the same number multiple times.
curr.pop_back();
target += candidates[i];
}
}

};
```

# Combination Sum II

> Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

> Each number in C may only be used once in the combination.

Note:

1. All numbers (including target) will be positive integers.

2. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

3. The solution set must not contain duplicate combinations.

1. 给定数组的所有值必须是正整数.（意味着我们加corner case invalid check的时候要检查T）
2. 答案数组中的值必须为升序排列.(我们要对数组进行排序)
3. 最终答案不能包含重复数组.

```c++
class Solution {
public:
vector > combinationSum2(vector &num, int target) {
vector> ret;
if(num.size() == 0 || target < 0) //invalid corner case check
return ret;
vector curr;
sort(num.begin(), num.end());
BackTracking(ret,curr,num,target,0);
return ret;
}

void BackTracking(vector>& ret, vector curr, vector num, int target, int level)
{
if(target == 0)
{
ret.push_back(curr);
return;
}
else if(target < 0)
return;
for(int i = level; i < num.size(); ++i)
{
target -= num[i];
curr.push_back(num[i]);
BackTracking(ret,curr,num,target,i+1);
curr.pop_back();
target += num[i];
while(i < num.size()-1 && num[i] == num[i+1]) //we add this while loop is to skip the duplication result
++i;
}
}

};
```

# Letter Combinations of a Phone Number

> Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given as below:

```
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
```

O(3^n)

```c++

class Solution {
public:
vector letterCombinations(string digits) {
vector ret;
/* for this question, we need to create a look-up dictionary */
vector dic;
string tmp;
dic.push_back(" ");
dic.push_back(" ");
dic.push_back("abc");
dic.push_back("def");
dic.push_back("ghi");
dic.push_back("jkl");
dic.push_back("mno");
dic.push_back("pqrs");
dic.push_back("tuv");
dic.push_back("wxyz");
combinations(ret,tmp,digits,dic,0);
return ret;
}

void combinations(vector& ret, string tmp, string digits, vector dic, int level)
{
if(level == digits.size())
{
ret.push_back(tmp);
return;
}

int index = digits[level]-'0';
for(int i = 0; i < dic[index].size(); ++i)
{
tmp.push_back(dic[index][i]);
combinations(ret,tmp,digits,dic,level+1);
tmp.pop_back();
}
}

};
```