# Question 1: Letter Combinations of a Phone Number

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

The question asks to explore a space of possibilities.

Backtracking: Exploring solutions to a problem and abandoning them if they are not suitable.

– Determine whether a solution exists

– Find a solution

– Find the best solution

– Count the number of solutions

– Print/find all the solutions

1. Find what choice(s) we have at each step. What different options are there for the next step?

2. For each valid choice:

(a)Make it and explore recursively. Pass the information for a choice to the next recursive call(s).

(b)Undo it after exploring. Restore everything to the way it was before making this choice.

`for(int j = 0; j < current.size(); j++){             curr.push_back(current[j]);            helper(digits,index+1,curr);            curr.pop_back();  }`

3. Find our base case(s). What should we do when we are out of decisions?

`class Solution {public:    string dic[10] = {{""},{""},{"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

`Input: n = 4, k = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]`

What is our base case in the Combinations Problem?

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

--

--

Software Developer working to become a better Software Developer everyday :)

Love podcasts or audiobooks? Learn on the go with our new app.

## Manvi Tyagi

Software Developer working to become a better Software Developer everyday :)