Backtracking Part 4— Combinations Problems(i)

We are gonna solve 5 questions related to combinations using backtracking, so for your and my convenience, I have divided the part 4 into 2 parts.

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.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

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

The question asks to explore a space of possibilities.

“Space of possibilities” — Did you get the hint? BACKTRACKING, YES

Let’s take a quick peek into “when to use backtracking”?

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

THOUGHT PROCESS FOR BACKTRACKING SOLUTION — 1

Let’s follow the “The Backtracking Brahmastra” :

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

Let’s say, I have input digit 23, what choice do I have for ‘2’, yes, right, pressing 2 will result in a,b or c. So, at each step, I have the choice of choosing any one alphabet for the corresponding number.

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

This part of code makes a choice with curr.push_back(current[j] and explores each of the choices recursively with helper(digits,index+1,curr) and curr.pop_back() is for undoing this particular choice and restoring everything as before so as to make the next choice.

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

What else, simply push the current combination to the final answer and return.

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

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

Example:

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

Did you read the solution approaches of Subsets Problem in part 2 of this “Selection Problems in Backtracking Series”? If yes, then there is no need for more explanation here. If you look at the problems carefully and analyze you will find that the solutions to both these problems are quite similar except the base case.

What is our base case in the Combinations Problem?

The size of our current answer or combination reaching the size k !!

Decision Tree

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

SOLUTION — 2

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

Next 3 questions in the next part :)

THANKS FOR READING!