Backtracking - Combination
在这个section里面,我们主要来过一下像leetcode里面类似combination这一系列的题,这类题应该归结为DFS+Backtracking。掌握了大体思想,注意一下边角处理就好,比如剪枝。
先来讨论一下第一题Combination.
Combination
Given two integers n and k, return all possible combinations of k numbers out of 1,2,…,n.
题目翻译:
给定两个整型数组n和k,要求返由k个数组成的combination,其实应该叫做组合. 这个combination应该是高中里面的组合。这k个数是在n中任选k个数,由题意可得,这里的k应该小于或等于n(这个条件不要忘了做validation check哦).
题目分析:
我觉得应该还有不少读者困惑什么是combination,这里我们先给一个例子比如n=3, k=2的条件下, 所有可能的combination如下:
[1,2], [1,3], [2,3]. 注意:[2,3]和[3,2]是相同的,我们只要求有其中一个就可以了.
所以解题的时候,我们要避免相同的组合出现.
解题思路:
看到这道题,首先第一想法应该是用递归来求解.如果要是用循环来求解,这个时间复杂度应该是比较恐怖了.并且,这个递归是一层一层往深处去走的,打个比方,我们一个循环,首先求得以1开始的看个数的combination,之后再求以2开始的,以此类推,所以开始是对n个数做DFS, n-1个数做DFS…所以应该是对n(n-1)…*1做DFS. 在程序中,我们可以加一些剪枝条件来减少程序时间.
时间复杂度:
在题目分析中,我们提到了对于对n,n-1,…,1做DFS,所以时间复杂度是O(n!)
代码如下:
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int>> ret;
if(n <= 0) //corner case invalid check
return ret;
vector<int> curr;
DFS(ret,curr, n, k, 1); //we pass ret as reference at here
return ret;
}
void DFS(vector<vector<int>>& ret, vector<int> 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:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
题目翻译:
给一个数组C和一个目标值T, 找出所有的满足条件的组合:使得组合里面的数字之和等于T,并且一些数字可以从C中午先选择。
注意:
所有给定的数字均为正整数.(这意味着我们加corner case invalid check的时候要加一条,如果给定T不是正整数,我们就没必要在往下进行了)
所有的答案组中要满足升序排列.
最后的答案数组不能包含重复答案.
题目分析:
这道题的大体思路和combination是相同的,不同的地方在于一个数字可以使用多次,这也造成了我们进行实现function的时候要注意的问题,也就是说,传入递归的参数不同于combination.
时间复杂度:
没什么好说的,和combination的时间复杂度是相同的.O(n!)
代码如下:
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int>> ret;
//corner case invalid check
if(candidates.size() == 0 || target < 0)
return ret;
vector<int> 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<vector<int>>& ret, vector<int> curr, vector<int> 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:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
题目翻译:
给定一个数组C和一个特定值T,要求找出这里面满足以下条件的所有答案:数组中数字的值加起来等于特定和的答案.
数组中每个数字只能用一次.(同three sum和four sum的解法)
注意条件:
- 给定数组的所有值必须是正整数.(意味着我们加corner case invalid check的时候要检查T)
- 答案数组中的值必须为升序排列.(我们要对数组进行排序)
- 最终答案不能包含重复数组.
代码如下:
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int>> ret;
if(num.size() == 0 || target < 0) //invalid corner case check
return ret;
vector<int> curr;
sort(num.begin(), num.end());
BackTracking(ret,curr,num,target,0);
return ret;
}
void BackTracking(vector<vector<int>>& ret, vector<int> curr, vector<int> 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"].
题目翻译:
给定一个字符串数字,返回这个字符串数字在电话表上可能的combination,一个map的电话键盘在上图已经给出.
题目分析:
这道题目的给出,具体的解题思路是和combination是相同的,不同的地方是我们要先建一个dictionary,以方便查找.之后用combination的相同方法,对于每一个数字,在dictionary中查找它所对应的说有的数字.
解题思路:
我是用字符串数组来构建这个dictionary的,用于下标代表数字,例如,下标为2,我的字典就会有这种对应的关系:dic[2] = “abc”.只要把给定数字字符串的每一个数字转换为int类型,就可以根据字典查找出这个数字所对应的所有字母.当然,再构建字典的时候,我们需要注意dic[0] = “”, dic[1] = “”.这两个特殊的case,因为电话键盘并没有这两个数字相对应的字符串.
时间复杂度:
O(3^n)
代码如下:
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> ret;
/* for this question, we need to create a look-up dictionary */
vector<string> 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<string>& ret, string tmp, string digits, vector<string> 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();
}
}
};