Backtracking Algorithm

           Backtracking Algorithm & Examples

  Backtracking is a general way to try all possible solutions(combinations)  in a problem. It recursively add next element into current list and remove this element when tried every possible combination with this element( after recursive call return ). It is a very useful to tool to let us try every possible solution with few lines of code and works pretty well in general case.  However, the drawback of this algorithm is time complexity. It usually have O(2^N) or O(N!) time complexity depending on different problems, which,again, mostly because it will try every possible combination.

Here are 4 examples that you may consider use backtracking approach to solve them.

        Example 1 :  Subsets 1 

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[  

[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] 

]

--------------------------------------------------------------------------------------------------------------------------

Analyze: This is a classic backtracking problem, where the power of backtracking may be fullly enbodyed. Besides it is also a little hard to come up with another solution.



Explain: If this is the first time you see a backtracking algorithm code, above code may seems a little weird to you. But it is actually very straightforward and common backtracking code. Here is few things I want to point out:
                      1. At line 11, we add current temp list into final results without any checking, because we need every possible combination as a part of answer in this problem. We may need to check certain properties before we add it into result list in other harder problems.
                   
                      2. At line 15, notice the for loop start from s ( start point) to end of the list, otherwise we will have many duplicate subsets. Besides, every recursive branch will have a different start point.
         
                     3.  Line 21 is a very crucial line of code, which make this algorithm works properly. This line of code will remove local added element from temp list and let it try other possible combination. For example for the example [ 1 , 2 , 3 ] above, after had [], [1], [1, 2], [1,2,3], recursive call will return, and this line of code will remove 3, then 2 from the list,which then we could try [ 1, 3] and have it in our results. ( It is very helpful that using pen and paper to trace what actually happened after recursive call return).

           Example 2: Subsets 2 

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[

[2],[1],[1,2,2],[2,2],[1,2],[]

]

--------------------------------------------------------------------------------------------------------------------------

Analyze: Just one change compare to the first example, so go ahead and try it by your self !

To deal with there may have duplicate one in our input array, we could:
      1. Sort the array and let possible duplicate one are adjacent to each other
      2. In the for loop if this element is same with previous one, we could then skip this one.

Here is the solution with those two changes:

         Example 3: Combination Sum 

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

--------------------------------------------------------------------------------------------------------------------------

Analyze: This example is a upgrade from the previous backtracking problem, where it requires the subsets of candidate set that will have a certain  property ( add up together to target value in this case).
So we would like to :
                     1. Remember the total sum of current temp list, and how many value we are away from the target value.
                    2. Check if temp list have this property before add it into our result list.

Here is what a solution may look like:

     Example 4: Remove Invalid Parentheses 

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

--------------------------------------------------------------------------------------------------------------------------
Analyze: This is a advanced example to use backtracking strategy that we need to keep our final result are all optimal and this string is valid parentheses all the time. But the whole idea is that a '(' or ')' is either exist or not exist in our final result.

  Here is the solution using backtracking:



Explain: I do want to point out that:

    1. From line 3 - 10, we are counting how may Left or Right parentheses are extra in our input array , and we use this value to test weather a solution is optimal.

    2. We also keep a filed called open, which will make sure at any given time we do not have Right parentheses more than Left one.

    3. Line 26 and 27 ( or 29, 30) is the idea that we either add this parentheses or we do not add it, which is a typical backtracking approach.

    4. Line 34, could remove the last element we added into this StringBuilder, which is the same as list remove method in previous examples.


Hope it helps you to understand backtracking algorithm. 


Enjoy Coding^^

Ye Jiang