🚀🚀 Backtracking Summary 🚀🚀

Template

void backtrack(arguments) {
	if (condition == true) { // base case , stop exploring
		result.push_back(current);
		return;
	}
	for (int i = num; i <= last; i++) {
		current.push_back(candidate); // Add candidate
		backtrack(arguments);
		current.pop_back();   // Discard candidate. This step is called backtracking.
	}
}

Problem	Input	Loop	Rec
Permutation	`nums[]`	`for (int i = 0; i < nums.size(); i++)`	`rec() independent of i`
Permutations II	`nums[]`	`for (int i = 0; i < nums.size(); i++)`	`rec():independent of i`

Permutations

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> curr;
        unordered_set<int> vis;
        rec(curr, nums, vis);
        return res;
    }
    void rec(vector<int>& curr, vector<int>& nums, unordered_set<int>& vis) {
        if (curr.size() == nums.size()) {
            res.push_back(curr);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (vis.count(i) == 0) {
                vis.insert(i);
                curr.push_back(nums[i]);
                rec(curr, nums, vis);
                vis.erase(i);
                curr.pop_back();
            }
        }
    }
};

Permutations -2

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> curr;
        unordered_set<int> vis;
        sort(nums.begin(), nums.end());
        rec(curr, nums, vis);
        return res;
    }
    void rec(vector<int>& curr, vector<int>& nums, unordered_set<int>& vis) {
        if (curr.size() == nums.size()) {
            res.push_back(curr);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (vis.count(i) == 1)
                continue;
            if (i > 0 && nums[i - 1] == nums[i] && vis.count(i - 1) == 0)
                continue;
            vis.insert(i);
            curr.push_back(nums[i]);
            rec(curr, nums, vis);
            vis.erase(i);
            curr.pop_back();
        }
    }
};

Problem	Input	Loop	Rec
Combination	`n,k`	`for (int i = idx; i <= n; i++)`	`rec(i+1)`
Combination Sum	`nums[] , target`	`for (int i = idx; i < candidates.size(); i++)`	`rec(i,target-candidate)`
Combination Sum II	`nums[] , target`	`for (int i = idx; i < cand.size(); i++)`	`rec(i+1,target-candidate)`
Combination Sum III	`9Ck with given sum`	`for (int i = idx; i <= 9; i++)`	`rec(i + 1,, target - candidate)`

Combination nCk (n choose k)

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combine(int n, int k) {
        vector<int> curr;
        rec(1, n, k, curr);
        return res;
    }

    void rec(int idx, int n, int k, vector<int>& curr) {
        if (k == curr.size()) {
            res.push_back(curr);
            return;
        }
        for (int i = idx; i <= n; i++) {
            curr.push_back(i);
            rec(i + 1, n, k, curr);
            curr.pop_back();
        }
    }
};

Combination Sum-1

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> curr;
        rec(0, curr, target, candidates);
        return res;
    }
    void rec(int idx, vector<int>& curr, int target, vector<int>& candidates) {
        // base case
        if (target < 0)
            return;
        if (target == 0) {
            res.push_back(curr);
            return; // controlled recursion
        }           // base case not dependent on idx
        for (int i = idx; i < candidates.size(); i++) {
            curr.push_back(candidates[i]);
            rec(i, curr, target - candidates[i], candidates);
            curr.pop_back();
        }
    }
};

Combination Sum-2

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum2(vector<int>& cand, int target) {
        vector<int> curr;
        sort(cand.begin(), cand.end());
        rec(0, curr, cand, target);
        return res;
    }
    void rec(int idx, vector<int>& curr, vector<int>& cand, int target) {
        // base case
        if (target < 0)
            return;
        if (target == 0) {
            res.push_back(curr);
            return;
        }

        for (int i = idx; i < cand.size(); i++) {
            if (i != idx && cand[i - 1] == cand[i])
                continue;
            curr.push_back(cand[i]);
            rec(i + 1, curr, cand, target - cand[i]);
            curr.pop_back();
        }
    }
};

Combination Sum-3

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> curr;
        rec(1, curr, n, k);
        return res;
    }

    void rec(int idx, vector<int>& curr, int target, int k) {
        if (curr.size() == k && target == 0) {
            res.push_back(curr);
            return;
        }
        for (int i = idx; i <= 9; i++) {
            curr.push_back(i);
            rec(i + 1, curr, target - i, k);
            curr.pop_back();
        }
    }
};

Problem	Input	Loop	Rec
Subsets	`nums[]`	`for(int i=idx;i<nums.size();i++)`	`rec(i+1)`
Subsets II	`nums[]`	`for(int i=idx;i<nums.size();i++)`	`rec(i+1)`

Subset-1

class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int>curr;
        rec(0,curr,nums);
        return res;
    }
    void rec(int idx,vector<int>&curr,vector<int>&nums){
        res.push_back(curr);
        for(int i=idx;i<nums.size();i++){
            curr.push_back(nums[i]);
            rec(i+1,curr,nums);
            curr.pop_back();
        }
    }
};

Subset-2

class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int>curr;
        sort(nums.begin(),nums.end());
        rec(0,curr,nums);
        return res;
    }
    void rec(int idx,vector<int>&curr,vector<int>&nums){
        res.push_back(curr);
        for(int i=idx;i<nums.size();i++){
            if(i!=idx && nums[i]==nums[i-1])continue;
            curr.push_back(nums[i]);
            rec(i+1,curr,nums);
            curr.pop_back();
        }
    }
};

Some other ways to get all possible subsets :
https://leetcode.com/problems/subsets/solutions/4764847/c-backtracking/

Palindrome Partitioning: https://leetcode.com/problems/palindrome-partitioning/submissions/

Code

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> partition(string s) {
        vector<string> curr;
        rec(s, curr, 0);
        return res;
    }
    void rec(string& s, vector<string>& curr, int start) {
        if (start == s.length()) {
            res.push_back(curr);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            string left = s.substr(start, i - start + 1);
            if (check_pall(left)) {
                curr.push_back(left);
                rec(s, curr, i + 1);
                curr.pop_back();
            }
        }
    }
    bool check_pall(string& s) {
        int low = 0;
        int high = s.length() - 1;
        while (low < high) {
            if (s[low] != s[high])
                return false;
            low++;
            high--;
        }
        return true;
    }
};

22.Generate parenthesis:

17.Letter-Combinations of a keypad :- 💡Solution💡

79.Word search 💡Solution w/o Pruning💡

980. Unique Paths III

HARD PROBLEMS

N-Queens: https://leetcode.com/problems/n-queens/
Visualizing N-queens problem is The best way to understand its working -
- N queen visualizer https://haseebq.com/n-queens-visualizer/ ⚡⚡
- Visualizer 2 https://www.cs.usfca.edu/~galles/visualization/RecQueens.html ⚡⚡
Sudoku solver: https://leetcode.com/problems/sudoku-solver/

VIsualize Sudoku solver :https://anhminhtran235.github.io/sudoku-solver-visualizer/ ⚡⚡

Practice Problems:
https://leetcode.com/problems/all-paths-from-source-to-target/
https://leetcode.com/problems/maximum-score-words-formed-by-letters Hard

Comments (0)