Backtracking

 

Backtracking

·      Backtracking is a problem-solving algorithmic technique that involves finding a solution by trying different options and undoing them.

·      need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku.

·      explores a different path until a solution is found or all possibilities have been exhausted.

 

GENERAL METHOD

Decision Problems: Here, we search for a feasible solution.

Optimization Problems: For this type, we search for the best solution.

Enumeration Problems: We find set of all possible feasible solutions to the problems of this type.

Graph C ,D, and F are all Hamiltonian graph 

Sum of the Subset

Given a set of positive integers, and a value sum, determine that the sum of the subset of a given set is equal to the given sum.

Input: set[] = {2, 3, 5, 6, 8, 10}, sum = 10  

Output = true  

There are three possible subsets that have the sum equal to 10.  

Subset1: {5, 2, 3}  

Subset2: {2, 8}  

Subset3: {10}  

SHARE

Milan Tomic

Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.

• 
• 
• 
• 
•