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

            }

        }

    }