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!)

代码如下:

  1. class Solution {
  2. public:
  3. vector<vector<int> > combine(int n, int k) {
  4. vector<vector<int>> ret;
  5. if(n <= 0) //corner case invalid check
  6. return ret;
  7. vector<int> curr;
  8. DFS(ret,curr, n, k, 1); //we pass ret as reference at here
  9. return ret;
  10. }
  11. void DFS(vector<vector<int>>& ret, vector<int> curr, int n, int k, int level)
  12. {
  13. if(curr.size() == k)
  14. {
  15. ret.push_back(curr);
  16. return;
  17. }
  18. if(curr.size() > k) // consider this check to save run time
  19. return;
  20. for(int i = level; i <= n; ++i)
  21. {
  22. curr.push_back(i);
  23. DFS(ret,curr,n,k,i+1);
  24. curr.pop_back();
  25. }
  26. }
  27. };

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.

题目翻译:
给一个数组C和一个目标值T, 找出所有的满足条件的组合:使得组合里面的数字之和等于T,并且一些数字可以从C中午先选择。

注意:

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

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

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

题目分析:
这道题的大体思路和combination是相同的,不同的地方在于一个数字可以使用多次,这也造成了我们进行实现function的时候要注意的问题,也就是说,传入递归的参数不同于combination.

时间复杂度:
没什么好说的,和combination的时间复杂度是相同的.O(n!)

代码如下:

  1. class Solution {
  2. public:
  3. vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
  4. vector<vector<int>> ret;
  5. //corner case invalid check
  6. if(candidates.size() == 0 || target < 0)
  7. return ret;
  8. vector<int> curr;
  9. sort(candidates.begin(),candidates.end()); //because the requirments need the elements should be in non-descending order
  10. BackTracking(ret,curr,candidates,target,0);
  11. return ret;
  12. }
  13. /* we use reference at here because the function return type is 0, make the code understand easily */
  14. void BackTracking(vector<vector<int>>& ret, vector<int> curr, vector<int> candidates, int target, int level)
  15. {
  16. if(target == 0)
  17. {
  18. ret.push_back(curr);
  19. return;
  20. }
  21. else if(target < 0) //save time
  22. return;
  23. for(int i = level; i < candidates.size(); ++i)
  24. {
  25. target -= candidates[i];
  26. curr.push_back(candidates[i]);
  27. BackTracking(ret,curr,candidates,target,i); //unlike combination, we do not use i+1 because we can use the same number multiple times.
  28. curr.pop_back();
  29. target += candidates[i];
  30. }
  31. }
  32. };

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.

题目翻译:
给定一个数组C和一个特定值T,要求找出这里面满足以下条件的所有答案:数组中数字的值加起来等于特定和的答案.

数组中每个数字只能用一次.(同three sum和four sum的解法)

注意条件:

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

代码如下:

  1. class Solution {
  2. public:
  3. vector<vector<int> > combinationSum2(vector<int> &num, int target) {
  4. vector<vector<int>> ret;
  5. if(num.size() == 0 || target < 0) //invalid corner case check
  6. return ret;
  7. vector<int> curr;
  8. sort(num.begin(), num.end());
  9. BackTracking(ret,curr,num,target,0);
  10. return ret;
  11. }
  12. void BackTracking(vector<vector<int>>& ret, vector<int> curr, vector<int> num, int target, int level)
  13. {
  14. if(target == 0)
  15. {
  16. ret.push_back(curr);
  17. return;
  18. }
  19. else if(target < 0)
  20. return;
  21. for(int i = level; i < num.size(); ++i)
  22. {
  23. target -= num[i];
  24. curr.push_back(num[i]);
  25. BackTracking(ret,curr,num,target,i+1);
  26. curr.pop_back();
  27. target += num[i];
  28. while(i < num.size()-1 && num[i] == num[i+1]) //we add this while loop is to skip the duplication result
  29. ++i;
  30. }
  31. }
  32. };

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:
Combination - 图1

  1. Input:Digit string "23"
  2. 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)

代码如下:

  1. class Solution {
  2. public:
  3. vector<string> letterCombinations(string digits) {
  4. vector<string> ret;
  5. /* for this question, we need to create a look-up dictionary */
  6. vector<string> dic;
  7. string tmp;
  8. dic.push_back(" ");
  9. dic.push_back(" ");
  10. dic.push_back("abc");
  11. dic.push_back("def");
  12. dic.push_back("ghi");
  13. dic.push_back("jkl");
  14. dic.push_back("mno");
  15. dic.push_back("pqrs");
  16. dic.push_back("tuv");
  17. dic.push_back("wxyz");
  18. combinations(ret,tmp,digits,dic,0);
  19. return ret;
  20. }
  21. void combinations(vector<string>& ret, string tmp, string digits, vector<string> dic, int level)
  22. {
  23. if(level == digits.size())
  24. {
  25. ret.push_back(tmp);
  26. return;
  27. }
  28. int index = digits[level]-'0';
  29. for(int i = 0; i < dic[index].size(); ++i)
  30. {
  31. tmp.push_back(dic[index][i]);
  32. combinations(ret,tmp,digits,dic,level+1);
  33. tmp.pop_back();
  34. }
  35. }
  36. };