Backtracking Algorithm

 I want to provide a toolkit and the patterns you can apply for backtracking problems. 

On a conceptual level, anything you have a problem that is solved by a series of decision, you make a wrong decision, and you'll have to backtrack into a previous decision. 

The way backtracking happen in recursive solutions can be extremely difficult to see. 

Imagine a robot is going through a maze. If the robot finds a dead end, it must be able to go back to the previous state.

The backtracking code is below, as well as an explanation.

This method adds specific items to a list except in the case that 0 elements are remaining for choices (which in consequence means that there are no paths left). 

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start){

//This snippet of code means that if there is nothing remaining, the backtracking is done for this specific

subset of the array. 

if(remain < 0) return;

//This snippet of code indicates that if there is a specific sum found, then add this arraylist to the list of desired sums. 

else if(remain == 0) list.add(new ArrayList<>(tempList));

//This snippet of code only runs whenever there is still values to add to this array. 

else{

    for(int i = 0; i < nums.length; i++){

         //add the particular element to the List that is to be added to the ArrayList. 

         tempList.add(nums[i]);

          //recall the backtrack algorithm to see if the list is still valid

         backtrack(list, tempList, nums, remain - nums[i], i + 1);

          //if the function returns, remove the last element of the list, and try the next number

//inside of the list. 

         tempList.remove(tempList.size() - 1); 

         

    }

}

}