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

代码如下:

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

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.     }
  14.     /* we use reference at here because the function return type is 0, make the code understand easily */
  15.     void BackTracking(vector<vector<int>>& ret, vector<int> curr, vector<int> candidates, int target, int level)
  16.     {
  17.         if(target == 0)
  18.         {
  19.             ret.push_back(curr);
  20.             return;
  21.         }
  22.         else if(target < 0) //save time
  23.             return;
  25.         for(int i = level; i < candidates.size(); ++i)
  26.         {
  27.             target -= candidates[i];
  28.             curr.push_back(candidates[i]);
  29.             BackTracking(ret,curr,candidates,target,i); //unlike combination, we do not use i+1 because we can use the same number multiple times.
  30.             curr.pop_back();
  31.             target += candidates[i];
  32.         }
  33.     }
  35. };

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.     }
  13.     void BackTracking(vector<vector<int>>& ret, vector<int> curr, vector<int> num, int target, int level)
  14.     {
  15.         if(target == 0)
  16.         {
  17.             ret.push_back(curr);
  18.             return;
  19.         }
  20.         else if(target < 0)
  21.             return;
  22.         for(int i = level; i < num.size(); ++i)
  23.         {
  24.             target -= num[i];
  25.             curr.push_back(num[i]);
  26.             BackTracking(ret,curr,num,target,i+1);
  27.             curr.pop_back();
  28.             target += num[i];
  29.             while(i < num.size()-1 && num[i] == num[i+1]) //we add this while loop is to skip the duplication result
  30.                 ++i;
  31.         }
  32.     }
  34. };

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)

代码如下:

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