KelvinMao

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

Analysis

此题和之前的 Combination Sum一样，都是应用回溯法，不过需要加上一个sum参数记录当前的数组中的元素的和，其余没有任何变化。

代码如下:

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;
    }
};
KelvinMao

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.

image

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.

Analysis

此题利用回溯法解决较为简洁。利用一个整形数组完成从键盘上的数字到键盘上的字符串的一个映射。

回溯函数中的整型变量tmp用于计算digits字符串中当前字符相对于'a'的偏移量，再减去2是因为map数组的索引是从0开始的，对于digits中的元素,其相对于'a'的偏移量应先减去2，其对应的字符串才是该元素对应的真正的在键盘上的字符串。

之后的迭代过程中，每次递归调用时，start的值应该+1，而不是常见的i+1，因为根据此题的要求，在固定了第一个数字对应的字符串中的某个字符后，下一个字符应该从下一个数字对应的字符串中的字符中去取。

例如:此题中的23,其combination中的第一个字符串的第一个元素来自于2，第二个元素来自于3.

代码如下:

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;
    }
};
KelvinMao

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

这道题是Permutations I的加强版，给出的序列中可能存在一些重复的元素，导致全排列中会出现一些重复的项目。

所以需要从简单的情况考虑，假如序列为[1,1,1,1]`，如果四个1代表不同的意义，则有

4!

种情况。但此题并不需要我们考虑顺序，即所有元素都代表相同的意义，所以实际上只有1种情况。

那么就需要给每个元素打上一个标签，给出一个布尔数组， 用两个布尔值来标记每个元素的状态。

考虑两种特殊情况:

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

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

第一种情况较好理解，但第二种就比较晦涩了。其实，第二种情况是为了保证相同元素之间的有序性。依然考虑边界条件[1,1,1,1]，如果当前元素为第二个1，但第一个1还没有被使用过，则应该跳过当前这个2，来保证是按顺序插入元素。

总结一下就是: 1.首先保证给定向量中元素的有序性（以便判断是否出现了重复元素）

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;
    }
};
KelvinMao

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

Analysis

这道题和之前遇到的回溯法应用有较大的不同，此题要求给出一个字符数组的全排列。

考虑手工计算全排列的过程，从序列中选择第一个数字，之后固定第一个数字，从后续中再选择数字，之后再固定第二个数字，选择第三个数字……循环往复直到获得一个长度与原字符数组相同的的新数组。

所以与之前的回溯法的实现不同，在首轮迭代的过程中，先将第一个数字也就是nums[0]压入栈中，使其固定，构造以nums[0]开头的所有排列；那么之后将以nums[1]为开头，构造所有排列，在此之前，需要将nums[0]从栈中弹出。

代码如下:

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;
    }
};
KelvinMao

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

Analysis

这道题与39.Combination Sum的区别在于，此题中元素只能使用一次，所以唯一需要改动的地方就是每次递归调用的深度需要+1，代码如下:

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;
    }
};