Backtracking is a technique that uses recursive algorithm by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (level of the tree) called as *BOUNDATION CONDITIONS*

## Acc to Wikipedia -

## Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably

constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate

("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution

__Ans__.When we have to get multiple solutions to a problem statement including subset problems, set problems etc. we use backtracking

Types of BackTracking Problems.

- Decision problem used to find a feasible solution of the problem.
- Optimisation problem used to find the best solution that can be applied.
- Enumeration problem used to find the set of all feasible solutions of the problem.

*root*(*P*): return the partial candidate at the root of the search tree.*reject*(*P*,*c*): return*true*only if the partial candidate*c*is not worth completing.*accept*(*P*,*c*): return*true*if*c*is a solution of*P*, and*false*otherwise.*first*(*P*,*c*): generate the first extension of candidate*c*.*next*(*P*,*s*): generate the next alternative extension of a candidate, after the extension*s*.*output*(*P*,*c*): use the solution*c*of*P*, as appropriate to the application

Some constraints ar provided to get the answer, if the set satisfies the problem then the traversal of the binary tree is continued else the compiler backtracks to another set of problems, in this way we can prevent all the unnecessary traversals of the tree that are not required

At the end we get all the possible subsets of solutions from the given data that satisfies the constraint relation.

Pseudo Code

Algorithm

Take a binary tree with two nodes having the sum of numbers uptill the traversal and next carrying the remaining array element's sum.

if the sum of values of Node 1 and 2 is greater than the given sum it continues the traversal else it backtracks.

Continues to check if the sum of values at Node 1 and Next element in the array is Less than or Equal to the given sum, else backtracks.

## Comments