Backtracking Part 4— Combinations Problems(i)

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

THOUGHT PROCESS FOR BACKTRACKING SOLUTION — 1

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[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.

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
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;
}
};

THANKS FOR READING!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manvi Tyagi

Manvi Tyagi

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