# Question 1: Letter Combinations of a Phone Number

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent.

`Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].`

## Let’s follow the “The Backtracking Brahmastra” :

`for(int j = 0; j < current.size(); j++){             curr.push_back(current[j]);            helper(digits,index+1,curr);            curr.pop_back();  }`
`class Solution {public:    string dic = {{""},{""},{"abc"},{"def"},{"ghi"},{"jkl"},{"mno"},{"pqrs"},{"tuv"},{"wxyz"}};    vector<string> ans;       void helper(string &digits, int index, string &curr){           if(index >= digits.size()){               ans.push_back(curr);               return;           }             string current = dic[digits[index]-'0'];            for(int j = 0; j < current.size(); j++){                 curr.push_back(current[j]);                helper(digits,index+1,curr);                curr.pop_back();          }    }    vector<string> letterCombinations(string digits) {        if(digits.size() == 0){                                 return ans;         }           string curr = {};           helper(digits,0,curr);           return ans;    }};`

# Question 2: Combinations

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

`Input: n = 4, k = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]`
`class Solution {public:    vector<vector<int>> ans;       void helper(vector<int> &arr, int index, int k, vector<int> &comb){        if(comb.size() == k){            ans.push_back(comb);            return;        }        if(index >= arr.size()) return;                 //include arr[index]        comb.push_back(arr[index]);        helper(arr,index+1,k,comb);                //don't include arr[index]        comb.pop_back();        helper(arr,index+1,k,comb);    }        vector<vector<int>> combine(int n, int k) {        vector<int> arr;        for(int i = 1; i <= n; i++){            arr.push_back(i);        }              vector<int> comb = {};        helper(arr,0,k,comb);        return ans;            }};`
`class Solution{public:  vector<vector<int>> ans;void subsets(vector<int> nums, int start, int k, vector<int> currset)  {    if (currset.size() == k)    {      ans.push_back(currset);      return;    }    if (start == nums.size())      return;for (int j = start; j < nums.size(); j++)    {      currset.push_back(nums[j]);      subsets(nums, j + 1, k, currset);      currset.pop_back();    }  }vector<vector<int>> combine(int n, int k)  {    vector<int> nums;    for (int i = 1; i <= n; i++)      nums.push_back(i);        subsets(nums, 0, k, {});    return ans;  }};`