# 216. Combination Sum III

## Description

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.

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]]



## code

class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & base,int sum,int start,int k,int n){
if(sum==n&&temp.size()==k){
res.push_back(temp);
return;
}
for(int i=start;i<base.size();++i){
temp.push_back(base[i]);
backtracking(res,temp,base,sum+base[i],i+1,k,n);
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> base={1,2,3,4,5,6,7,8,9};
vector<vector<int>> res;
vector<int> temp;
backtracking(res,temp,base,0,0,k,n);
return res;
}
};


# 17. Letter Combinations of a Phone Number

## Description

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 below.

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


Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

## code

class Solution {
private:
void backtracking(vector<string> & result,string & temp,string & digits,int start,int * map){
if(start==digits.size()){
result.push_back(temp);
return;
}
int tmp=digits[start]-'0'-2;
for(int i=map[tmp];i<map[tmp+1];++i){
temp.push_back('a'+i);
backtracking(result,temp,digits,start+1,map);
temp.pop_back();
}
return;
}
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
string temp="";
int map[10]={0,3,6,9,12,15,19,22,26};
backtracking(result,temp,digits,0,map);
return result;
}
};


# 47. Permutations II

## Description

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2] have the following unique permutations:

[
[1,1,2],
[1,2,1],
[2,1,1]
]


## Analysis

4!


1.如果当前元素已经被使用过，则在当前循环中应该被跳过

2.如果当前元素在之前出现过，且前一个元素还没有被使用过，则也应当被跳过。

2.对于需要跳过的元素，其判断依据为:

## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & templist,vector<int> & nums,bool * used){
if(templist.size()==nums.size()){
res.push_back(templist);
return;
}
for(int i=0;i<nums.size();++i){
if(used[i]||i>0&&nums[i]==nums[i-1]&&!used[i-1])     continue;
used[i]=true;
templist.push_back(nums[i]);
backtracking(res,templist,nums,used);
used[i]=false;
templist.pop_back();
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
bool used[nums.size()]={false};
vector<vector<int>> res;
vector<int> templist;
sort(nums.begin(),nums.end());
backtracking(res,templist,nums,used);
return res;
}
};


# 46. Permutations

## Description

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]


## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & nums){
if(temp.size()==nums.size()){
res.push_back(temp);
return;
}
for(int i=0;i<nums.size();++i){
if(find(temp.begin(),temp.end(),nums[i])!=temp.end())   continue;
temp.push_back(nums[i]);
backtracking(res,temp,nums);
temp.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
backtracking(res,temp,nums);
return res;
}
};


# 40. Combination Sum II

## Description

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:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]


## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
if(remain<0)      return;
if(remain==0){
res.push_back(temp);
return;
}
for(int i=start;i<candidates.size();++i){
if(i>start&&candidates[i]==candidates[i-1])     continue;
temp.push_back(candidates[i]);
backtracking(res,temp,candidates,remain-candidates[i],i+1);
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> temp;
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
backtracking(res,temp,candidates,target,0);
return res;
}
};
`