**leetcode: Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

My Submissions

Total Accepted: 62920 Total Submissions: 233476 Difficulty: Medium

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.

Subscribe to see which companies asked this question

Hide Tags

 Backtracking String

Show Similar Problems

Backtracking for all

```````````````````````````````````````````````````````````````````````````````

A very classical BT problem.
the jumping for  i using for loop,
while the jumping for j using j+1 within BP function.

////////////////////////////////////////

class Solution {

 public:

                 void backTrac(vector<string>&source, vector<string>&res, string tmp, int i, int j, string digits){

                                 if (j== digits.size()){

                                                 res.push_back(tmp);

                                                 return;

                                 }

                                 else{

                                                 int J = (digits[j] - '0');

                                                 //if (J<0 || J>9)return;

                                                 for (int i=0; i<source[J].size(); i++){

                                                                 //for (; j<digits.size(); j++){

                                                                                 tmp.push_back(source[J][i]);

                                                                                 backTrac(source, res, tmp, i, j + 1, digits);

                                                                                 //--j;

                                                                                 tmp.pop_back();

                                                                // }

                                                 }

                                                 //return;

                                 }

                 }

                 vector<string> letterCombinations(string digits) {

                                 //compose the vector for mapping

                                 vector<string> source = { "","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

                                 vector<string> res;

                                 if(digits.size()==0)return res;

                                 string tmp;

                                 int i = 0, j = 0;

                                 backTrac(source, res, tmp, i, j, digits);

                                 return res;

                 }

 };

Leetcode: Generate Parentheses

22. Generate Parentheses

My Submissions

Total Accepted: 70088 Total Submissions: 203144 Difficulty: Medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Subscribe to see which companies asked this question

Hide Tags

 Backtracking String

Show Similar Problems

````````````````````````````````````````````````````````````````

Backtracking:

Different from the "combination-Sum", it doesn't need to use the for loop inside the backtracking. 
And the condition to judge it's valid or not:

               if (l<r || len >= n && l != r)return;

               else if (l == r && len == n) { res.push_back(tmp); return; }

/////////////////////////////////////////////

class Solution {

 public:

        void backTrac(vector<string>& res, string & tmp, int l, int r, int len, int n){

               if (l<r || len >= n && l != r)return;

               else if (l == r && len == n) { res.push_back(tmp); return; }

               else{

                      ++len;

                      if (len>n)return;

                      //test '('

                      ++l;

                      tmp.push_back('(');

                      backTrac(res, tmp, l, r, len, n);

                      --l;

                      tmp.pop_back();

                      //test ')'

                      ++r;

                      tmp.push_back(')');

                      backTrac(res, tmp, l, r, len, n);

                      tmp.pop_back();

                      --r;

               }

               return;

        }

        vector<string> generateParenthesis(int n) {

               vector<string> res;

               string tmp;

               int l = 0, r = 0, len = 0, nn = 2 * n;

               backTrac(res, tmp, l, r, len, nn);

               return res;

        }

 };

Leetcode: Combinations

77. Combinations

My Submissions

Total Accepted: 61469 Total Submissions: 189601 Difficulty: Medium

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

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

Subscribe to see which companies asked this question

Hide Tags

 Backtracking

Hide Similar Problems

 (M) Combination Sum (M) Permutations

```````````````````````````````````````````````````````````````````````````````

Backtracking:

Similar as Combination Sum I, II, III. 

///////////////////////////////////////////////

//CODES

class Solution {

public:

   void backTrac(vector<vector<int>>& res, int n, int k, vector<int>& tmp, int len, int i){

       if(len==k) {res.push_back(tmp); return;}

       else{

           for (;i<n;i++){

               tmp.push_back(i+1);

               len++;

               backTrac(res, n, k, tmp, len, i+1);

               len--;

               tmp.pop_back();

           }

           return;

       }

   }

    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> res;

        vector<int> tmp;

        int len=0, i=0;

        backTrac(res, n, k, tmp, len, i);

        return res;

    }

};

Leetcode: Combination Sum III

216. Combination Sum III

My Submissions

Total Accepted: 20030 Total Submissions: 61524 Difficulty: Medium

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.

Ensure that numbers within the set are sorted in ascending order.

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Array Backtracking

Hide Similar Problems

 (M) Combination Sum

````````````````````````````````````````````````````````````````````

BackTracking:

similar as Combination Sum I, and II. 

///////////////////////////////////////////

//codes

class Solution {

public:

    void backTrac(vector<int>& source, vector<int> tmp, vector<vector<int>>& res, int len, int i, int target, int sum, int k){

        if(sum==target && len==k) {res.push_back(tmp); return;}

        else if(sum>target || len>k) return;

        else{

            for (;i<source.size(); i++){

                len+=1;

                sum+=source[i];

                tmp.push_back(source[i]);

                if(len>k)return;

                if(sum>target)return;

                backTrac(source,tmp,  res,  len,  i+1,  target, sum, k);

                sum-=source[i];

                tmp.pop_back();

                len--;

            }

            return;

        }

    }

    vector<vector<int>> combinationSum3(int k, int n) {

        //check input

        //if()

        vector<vector<int>> res;

        vector<int> tmp;

        vector<int> source={1, 2,3,4,5,6,7,8,9};

        int len=0,i=0,target=n, sum=0;

        backTrac(source,tmp,  res,  len,  i,  target, sum, k);

        return res;

    }

};

revised:

//////////////////////////////////////////////
class Solution {
public:
void BT(int k, int n, int i, vector<vector<int>> &res, vector<int> tmp, vector<int> &nums){
if(k==1){
for(int j=i;j<nums.size();j++){
if(nums[j]==n){
tmp.push_back(nums[j]);
res.push_back(tmp);
tmp.pop_back();
return;
}
else if(nums[j]>n){
return;
}

}
}
else{
for(int j=i;j<nums.size();j++){
tmp.push_back(nums[j]);
BT(k-1, n-nums[j], j+1, res, tmp, nums);
tmp.pop_back();
}

}
}


    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
vector<int> tmp, nums={1,2,3,4,5,6,7,8,9};
BT(k, n, 0, res, tmp, nums);
return res;
    }

};