21. Backtracking
- pow fn/ BINARY EXPONENTIATION✅
- print all subsequences/ POWER SET✅
- print all subsequences with sum k✅
- subset sum✅
- count no. of subsequences with sum k✅
- check if any one subsequence with sum k exists or not✅
- combination sum-1,2✅
- subset -2✅
- N queens
- Sudoku solver
- Rat Maze problem
- M-coloring (graphs)
- Palindrome partitioning
- k-th Permutation sequence
- print all permutations of an array/ string
LEC : 6 & 7 most imp...
---------------------------------------------------------------------------------------------------------
POW(x,n)-(binary exponentiation)
-----------------------------------------------------------------------------------------------------------
Call stack aise maano ki ek call mein kisi line of code pe vo line abhi execute ni hori vo bolri ki ruko abhi hoke aati hu zara and then vo dusri fn call mein chali gayi and so on...
---------------------------------------------------------------------------------------------------------------
Two types of recurssion-
1. parametrised- fn mein ek parameter m hi ans update hota rahega and last m fn us parameter ko print krdega...
2. functional- function return krega last m ans ko
---------------------------------------------------------------------------------------------------------------
0. Printing all Subsequences-
Power Set
we can get all subsequences by recursion by using pattern of take or not take for each element of array...for every index of the array we have 2 options
----------------------------------------------------------------------------------------------------------------------
1. ) printing all subseq whose sum is k-
Trick to turn code of printing all recursions to a code of printing any one of the recursion-
2. checking if any one subseq with sum k exists -
3. counting no of subsq-
for N calls-
another method can be using a cnt variable
----------------------------------------------------------------------------------------------------------------------
4.) Combination Sum-1
- return all possible unique subsequences which sum up to target sum
- an element from the array can be taken any no. of times
Method-1: simple
5.) Combination Sum-(no duplicates)
- return all possible unique subsequences which sum up to target sum
- an element from the array can be taken at most once
- return combinations in lexicographically sorted order
Method-1: use prvs method with just ind being ind+1 even after picking an elmt-->itna hi kroge agar toh agar given array mein repeated elements honge toh combinations unique nhi aayenge
: we will store 2d vector elmts in a set to avoid duplicates
time- (2^n)*n*(log(2^n))
----------------------------------------------------------------------
Method-2: Loop mein recursion
set mein insertion mein logM time ka extra factor aayega, to avoid that we go by below approach-
i>ind ki cond isliye lagayi hai taaki same wale skip bas same level pe ho in the recursion tree and not in upper and lower level...
---------------------------------------------------------------------------------------------------------------------------Patterns in Recursion-
1. binary recursion-
- take or not take
- here to avoid duplicates we need set of vectors and sorting the original vector in the starting
2. recursion inside loop-
- to generate multiple branching paths from a single decision point
- easier to avoid duplicates
- used when we want effective soln in ques where there are duplicates in the input but we want unique outputs
------------------------------------------------
NOTE-
1. if n diff elements, then there are 2^n subsequences with no duplicates
2. adding elmts into a data structure works in linear time complexity unless set.
-------------------------------------------------------------------------------------------------------------
6.) Subsets sum -1:
Given an array print all the sum of the subset generated from it, in the increasing order.
--> simple
7.) Subsets-2:
print all subsets of an array which contains duplicates,
but we want only unique subsets, e.g., {1,2,2} arr mein {1,2} bas ek baar hi chahiye subsets mein...
BRUTE: pehle 2d vector me bharlo fir set mein krdo;
BETTER:
-------------------------------------------------------------------------------------------------------------------------
8.) Print All permutations-
(approach-1) :
SPACE- n+n
------------------------------------------------------
------------------------------------------------------
(approach-2) :
NO extra space
-----------------------------------------------------------------------------------------------------------------------
9.) N- Queens:
ek col ke alag alag posn pe check kro ek level pe
-----------------------------------------------------------------------------------------------------------------------------
optimisation for searching and checking valid posn -
instead of doing it in 3n we can use hashing-
hashing for going left and diag down-
hashing for left and diag up
10.) SUDOKU solver-
11.) Palindrome partitioning-
12.) Rat Maze Problem-
we want different ans paths in lexicographical order, i.e., DLRU
for example below- DDRDRR and DRDDRR mein DD se start hora pehla aur dusra DR se
ALTER-
13. ) Permutation Sequence-
BRUTE- make all permutations and then store in data structure and sort and extract
OPTIMAL-
Comments
Post a Comment