virat9358/backtrack

BackTracking Overview

  **Generate parenthesis**
  for n we get (2n C n)/(n+1)
  we will make open(n) and close(0) parameter
  if(open)call(open-1, close+1)
  if(close)call(open, close-1)
   
  Palindrome Partitioning
   aab     (0)ab   (0)b
 0:  (a ->   a  ->   b)   -tmp_ans
 1: (aa->b) ab            -tmp_ans        aa is palindrome so it will go into fun and get b
 2:  aab                  -tmp_ans
   fun(s):
	   base is s.size == 0, push
	   for i = 0 to n:
	   	tmp = s.substr(0 ,i + 1) we will get (a, aa, aab)
	   	if palindrome :
	   	    push()
	   		fun(s.substr(i+1))
	   		pop
	   		
  Permuation with spaces
  just create all possibilites with space include or not condition
  for edge case(last character) push it without space 
  
  Array Partition
  to get absolute diff between any pair of elements we need to sort
  check start and start + k -1, is basic condition
  if it satisifies go to fun(start+1)
  
  Largest num in k swaps
  find all possibilities (by decr k) and get the max, for every combination recursively 
  

NOTE

  Question: Help the odd man out