I won't explain what backtracking is or how recursion works, If you are interested that there are infinite numbers of resources on youtube. What I'm gonna do is put all the major backtracking problems under one umbrella so you can master the pattern. I won't be drawing diagrams or explaining code, I don't think that's useful unless you dry run yourself.
Intuition: We need all permuations, how to find permutaion of [1,2,3] ? Fix one of them for first index then repeat same thing for indices.
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& nums, int idx) {
int n = nums.size();
if (idx >= n) {
ans.push_back(nums);
return;
}
for (int i = idx; i < n; i++) {
swap(nums[i], nums[idx]);
solve(ans, nums, idx+1);
swap(nums[i], nums[idx]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> temp;
solve(ans, nums, 0);
return ans;
}
};*** Q2. https://leetcode.com/problems/permutations-ii/description/**
Intuition: Same as previous but problem but we have duplicates here. Only thing to keep in mind is we don't want same number fixed at same index twice, so we check for it and skip. I'll share my implementation, you can do your own.
class Solution {
public:
void solve(vector<vector<int>>& ans, vector<int>& nums, int idx) {
int n = nums.size();
if (idx >= n) {
ans.push_back(nums);
return;
}
unordered_set<int> st;
for (int i = idx; i < n; i++) {
if(st.find(nums[i]) != st.end()) continue;
st.insert(nums[i]);
swap(nums[i], nums[idx]);
solve(ans, nums, idx+1);
swap(nums[i], nums[idx]);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> temp;
solve(ans, nums, 0);
return ans;
}
};*** Q3. https://leetcode.com/problems/subsets/description/**
Intuition: How to calculate subsets? At each index, we have a choice (as in your life), either take it or leave it. There is a bit manipulation method for this which is pretty classy, explore if interested.
class Solution {
public:
vector<vector<int>> output;
int n, k;
void backtrack(int first, vector<int> curr, vector<int>& nums) {
output.push_back(curr);
for (int i = first; i < n; i++) {
curr.push_back(nums[i]);
backtrack(i + 1, curr, nums);
curr.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
vector<int> curr;
backtrack(0, curr, nums);
return output;
}
};*** Q4. https://leetcode.com/problems/subsets-ii/description/**
Intuition: Same as previous problem but with duplicates. Here we don't let's say we decide to skip a element, then it does not make sense to pick it again, right? It's leetcode's version of don't go back to your ex. How to avoid duplicates? Either sort the array first, then skip continuous same elements. You can use frequency array/ map too. If you think harder you might think why I did not sort and skip in permuatation II problem? Because, I was swapping the elements, and then array won't be sorted anymore, right?
class Solution {
public:
vector<vector<int>> output;
int n, k;
void backtrack(int first, vector<int> curr, vector<int>& nums) {
output.push_back(curr);
for (int i = first; i < n; i++) {
if(i!= first && nums[i] == nums[i-1])
continue;
curr.push_back(nums[i]);
backtrack(i + 1, curr, nums);
curr.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(begin(nums), end(nums));
n = nums.size();
vector<int> curr;
backtrack(0, curr, nums);
return output;
}
};*** Q5.https://leetcode.com/problems/combination-sum/description/**
Intuition: Same old take it or leave it.
class Solution {
public:
vector<vector<int>> ans;
void solve(vector<int>& nums, vector<int>& temp, int target, int idx){
if(target == 0){
ans.push_back(temp);
}
if(target < 0 or idx == nums.size())
return;
for(int i=idx; i<nums.size(); i++){
temp.push_back(nums[i]);
solve(nums, temp, target - nums[i], i);
temp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
vector<int> temp;
solve(nums, temp, target, 0);
return ans;
}
};- Q6. https://leetcode.com/problems/combination-sum-ii/
Intuition: Again we don't want duplicates, so what do we do? Yes, you guessed it, sort the array and skip just as we did in subsets II. You can also use frequency vector/ map too.
class Solution {
public:
vector<vector<int>> ans;
void solve(vector<int>& nums, vector<int>& temp, int target, int idx){
if(target == 0){
ans.push_back(temp);
}
if(target < 0 or idx == nums.size())
return;
for(int i=idx; i<nums.size(); i++){
if(i != idx && nums[i] == nums[i-1])
continue;
temp.push_back(nums[i]);
solve(nums, temp, target - nums[i], i+1);
temp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
sort(begin(nums), end(nums));
vector<int> temp;
solve(nums, temp, target, 0);
return ans;
}
};*** Q7. https://leetcode.com/problems/combination-sum-iii/description/**
Intuition: No intuition, just rote learning
class Solution {
public:
vector<vector<int>> ans;
void solve(int k, int sum, int curr, vector<int> & temp){
if(k == 0){
if(sum == 0)
ans.push_back(temp);
return;
}
for(int x = curr; x <= 9; x++){
temp.push_back(x);
solve(k-1, sum - x, x+1, temp);
temp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> temp;
solve(k,n,1,temp);
return ans;
}
};Q8. https://leetcode.com/problems/generate-parentheses/description/
Intuition: No intuition, just do some dry run, logic is easy
class Solution {
public:
vector<string> ans;
void solve(int l, int r, int n, string s){
if(l == n && r == n){
ans.push_back(s);
return;
}
if(r > l or l > n or r > n)
return;
if(l > r)
solve(l, r+1, n, s+")");
solve(l+1, r, n, s+"(");
}
vector<string> generateParenthesis(int n) {
string s;
solve(0, 0, n, s);
return ans;
}
};Q9. https://leetcode.com/problems/word-search/description/
Intuition: Start from every index, search for the world, same old backtracking trick, just how to navigate is to be figured out, pro tip: learn this navigation method, used in lots of matrix related problems
class Solution {
private:
vector<vector<char>> board;
int ROWS;
int COLS;
bool backtrack(int row, int col, string& word, int idx){
if(idx == word.size())
return true;
if(row < 0 || row == ROWS or col < 0 or col == COLS or board[row][col] != word[idx])
return false;
bool ans = false;
board[row][col] = '#';
vector<pair<int,int>> directions = {{1,0},{0,1},{-1,0},{0,-1}};
for(auto direction:directions){
ans = backtrack(row + direction.first, col + direction.second, word, idx+1);
if(ans)
break;
}
board[row][col] = word[idx];
return ans;
}
public:
bool exist(vector<vector<char>>& board, string word) {
this->board = board;
ROWS = board.size();
COLS = board[0].size();
for(int row = 0; row < ROWS; row++){
for(int col = 0; col < COLS; col++){
if(backtrack(row, col, word, 0))
return true;
}
}
return false;
}
};Will add more if I get time. Go to problems page and sort by backtracking page if you want to do some mental gymnastics by yourself.
Remember, manipulate bits, not people :)