Some Basic Pattern for Some basic backtracking problems

Subsets:

Subsets are basically generated by all possible subsequences in the given order and are obviously unique and here an empty subset possible. If a number of elements are N, then 2^N subsets possible.

Se can solve it using Backtracking, so simply rest of the problem including this one we will see code, so we can better understand.

First sort the given array,

    vector<vector<int>>ans;

    void sub(vector<int>&a, int pos, vector<int>&cur){

        ans.push_back(cur); // include to answer

        for(int i = pos; i<a.size(); i++){

            cur.push_back(a[i]);//take

            sub(a, i+1, cur); // move forward

            cur.pop_back();// dont take, backtrack

        }

      }


Subsets with many occurrences:
This time we have to generate subsets but don't generate the same subsets multiple times, but the given array can have duplicate values.

Example:

Input

[1,2,2]

Wrong Output

[[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]

Right Expected

[[],[1],[1,2],[1,2,2],[2],[2,2]]

  vector<vector<int>>ans;

  void gen(vector<int>&a, int pos, vector<int> &cur){

        ans.push_back(cur);

        for(int i = pos; i<a.size(); i++){

            if(i>pos and a[i-1] == a[i])continue;

            cur.push_back(a[i]); //take

            gen(a, i+1, cur); // move forward;

            cur.pop_back(); // dont take, move forward

        }

    }

Permutations Generate:

Suppose the given array is [1,2,3], there are 3! permutations possible.
That is [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
The general idea is just swapping their positions and simply adding them to the answer.

  vector<vector<int>>ans;

  void per(int pos, vector<int>&a){

        if(pos==a.size()-1)ans.push_back(a);

        for(int i = pos; i<a.size(); i++){

            swap(a[i], a[pos]);

            per(pos+1, a);

            swap(a[i], a[pos]);

        }

    }
Permutations Generate with duplicates value:

This time given array can contain duplicate values. Solving approach same as before just we have to handle this case.

vector<vector<int>>ans;

map<vector<int>, bool>mark;

void per(int pos, vector<int>&a){

        if(pos==a.size()-1 and !mark[a]){

            ans.push_back(a);

            mark[a] = 1;

        }

        for(int i = pos; i<a.size(); i++){

            swap(a[i], a[pos]);

            per(pos+1, a);

            swap(a[i], a[pos]);

        }

}

Combinations Sum:

Suppose we have given an array and a target value. we need to make a list of arrays from the given array so that their sum is given target. We can use the same elements multiple times.

For more understanding lets see an example,
Array = [2,3,6,7], target = 7,

all possible array's are, [[2,2,3],[7]]

For solving backtracking problems we need to choose a choice, what should I pick or what should I don't need to pick?

So, here we have two choices, pick the current value and don't pick the current value.

    vector<vector<int>>ans;

    void gen(int pos, vector<int>& candidates, int target,vector<int>&cur_v){

        if(target  < 0)return;

        if(target == 0)ans.push_back(cur_v);

        for(int i = pos; i<candidates.size(); i++){

            cur_v.push_back(candidates[i]);

            gen(i, candidates, target - candidates[i], cur_v); // we dont need to move forward, because we use same element again

            cur_v.pop_back(); // dont use current element

        }

    }

Combinations sum can't reuse same element's:

This time we don't need to use the same position again and the given array can contain multiple values.

        vector<vector<int>>ans;

        map<vector<int>, int>mark;

    void gen(int pos, vector<int>& candidates, int target,vector<int>&cur_v){

        if(target  < 0)return;

        if(target == 0){

            ans.push_back(cur_v);

        }

        for(int i = pos; i<candidates.size(); i++){

            if(i > pos and candidates[i]==candidates[i-1])continue; // ignore duplicates

            cur_v.push_back(candidates[i]);

            gen(i+1, candidates, target - candidates[i], cur_v); // move forward, because we don't use same element again

            cur_v.pop_back(); // dont take current element

        }

    }

Palindrome Partitioning:
We all know what is palindrome right ? Now, we have given a string and and we have to generate number of all possible palindrome partition from this string.

For example, we have given a string "aab"
palindrome partition can be, {'a','a','b'}, {'aa', 'b'}

vector<vector<string>>ans;

    bool palin(string s, int l, int r){

        while(l <= r){

            if(s[l] != s[r])return false;

            l++, r--;

        }

        return true;

    }

    void part(int pos, string s, vector<string>cur_v){

        if(pos == s.size()){

            ans.push_back(cur_v);

        }

        for(int i = pos; i<s.size(); i++){

            if(palin(s,pos,i)){

                string t = s.substr(pos, i-pos+1);

                cur_v.push_back(t);

                part(i+1, s, cur_v);

                cur_v.pop_back();

            }

        }

    }

Permutation Generate using Backtracking

Permutation means an arrangement of some elements into a sequence of order. Suppose an array A[] = {1,2,3}, its all possible permutation is, 

{ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] }, Permutation calculate by N! ( N factorial). N is the size of an array.

So here N is 3, so 3! means 6 possible permutations can be generated.

Before Solving permutation, we know how subsets can be generated. In subsets calculations, Every size of subsets can be different, right?

But, Here in permutation every size of its arrangement is the same as the given array size, right ?
So, what's happening here, we just changing their position, isn't it?

See, {1,2,3}, {1,3,2}. We just change their position 2 to 3 , 3 to 2.

So, we don't need the extra array to calculate every arrangement of permutation, but in subsets calculation, we have used an extra array so that we can store all possible subsets because of their different sizes.

That means, here permutation calculation we can just swap their position.

So, our state is position, and base case is if position reach at the end of the array then simply we can add this arrangement to our answer.

But we need to do a simple operation, just run a loop from the current position and swap every element with the current position and again call another recursive with position+1.
At the same time after calling another recursive function, we need to re-swap their position, here backtracking happening.

Simple code: 

vector<vector<int>>ans;

void per(int pos, vector<int>&a){

        if(pos == a.size()-1){

            ans.push_back(a);

            return;

        }

       for(int i = pos; i<a.size(); i++){

           swap(a[i], a[pos]); // changing their position

           per(pos+1, a);

           swap(a[i], a[pos]); // backtracking

       }

}

You can submit your solution here.

Parenthesis Generate using Backtracking

Given Parenthesis size N, we have to generate all possible Parenthesis Of length N. One length = (), Two lengths = ()(),(())

Suppose N = 3,

Possible parenthesis are,

((())), (())(), ()(()), ()()(), (()())

Approach:
Easy to understand that, if we add n open brackets '(', then obviously we have to add n close brackets ')' also.

So, somehow we have to keep track of these two things. Now, what can be our base case? if we add n '(' brackets and n ')' brackets then simply we can add the string to our answer and return.

Our recursion code will look like this

void para(int l, int r, vector<string>&ans, string s){

        if(l == 0 and r==0){

            ans.push_back(s);

            return;

        }

        else{

            if(l > 0){

                para(l-1, r, ans, s+'(');

            }

            if(r > l){

                para(l, r-1, ans, s+')');

            }

        }

    }

We can start from " para(n, n, ans, s) " here. Initially, we pass n open and n close brackets, a string vector(ans), and an empty string s.

For better understanding take a pen and paper and illustrate this stuff.


You can submit your solution here.

Subsets and Combinations generate using Backtracking

What are subsets?
Subsets are generating all possible subsequences in a given order. If there are N elements then possible subsets can be found 2^N.

Suppose given array is A[] = {1,2,3}, possible subsets is, {}, {1},{1,3}  etc total 2^3 = 8 subsets can generate, but {2,1} isn't a subset, because this one breaks the order.

We can solve this problem using backtracking. What can be our state? We need to traverse the array, so we need a position parameter, that's enough.

See the image, here we tried to illustrate the whole backtracking functions that generate all possible subsets.
So, what will be our operations, see every time we can pick the current value of the array or we can avoid the current value and move to forward.

Base case? if position reached the end of the array, we can simply add this subset to our answer, and return. 
 

Combinations:
Combinations are also the same as a subset, but here we just generate using fixed sizes subsets.

State same, we just have to modify base cases, Why?  because we have to generate k sizes subsets only and if position reached at the end of the array then simply we have to return from there. So, two base cases.

Introduction to Recursion and Backtracking

Recursion:

    what is recursion?

        what is recursion?

            what is recursion?

                what is recursion?

Before learning Recursion you must have knowledge about function, parameters, and its return type. They are very easy to learn, just google or search on youtube about "function".

Recursion is a method when a function calls itself and works with some other inputs. Every recursion function has almost the same following components.

void f(// State ){

    // Base or terminating case

    // Operations on state, and possible calls to f() function again

}

The state is nothing but the parameters of a function.
Recursion is a kind of infinite loop, not like that but you can imagine - every time the function call by itself so after some operations, you must have to stop the process, this is called base case or terminating case.

For better understanding let's illustrate, calculating the sum of an array obviously using recursion.

Look at the picture carefully I have tried to illustrate the internal view of recursion, what happened when we call a recursion function, it actually creates another recursion function and stores all of them in a Stack. After reaching the base case it stops storing function in stack, and we know stack work with a property that is LIFO(Last-In-First-Out), so the last calling function will operate first. We see here the 5th function that returns 0 after that will be removed from the stack after another function will be called and so on. Initially, the main function was already stored in the stack, that's why after processing all other functions, the main function operates in the last.

So, now we know what is recursion and how it works. If we try to sum up what we need to do when we solve recursive related problems that are,

1. What is the state?
2. What is the best case?

3. And finally what do we want to achieve?

Backtracking:
Backtracking is similar to recursion. It is actually a general method of trying all possible solutions to a problem using recursively.

We can't solve all problems using backtracking, because generating a number of possible solutions can be huge, so it is only applicable if and only if the number of inputs is small and at the same time there is no other better algotithm.


For better understanding, we need to solve problems using backtracking. Near future, I will discuss some problems. For now try some problems given below.

Related problems,
Climbing Stairs - Easy

Combinations - Medium

Permutations - Medium

Generate Parentheses - Medium

N-Queens - Hard

N-Queens II - Hard