[Leetcode for Interviews]DFS, BFS, and Backtracking II – How to backtrack? Detailed Explanations with Examples

Backtracking is a general algorithm … 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.

https://en.wikipedia.org/wiki/Backtracking

Note: This is the second part for BFS, DFS and Backtracking. The first part is here: [Leetcode for Interview]DFS, BFS, and Backtracking I.

What is backtracking?

While applying DFS to search through a graph, once we determine that the subgraph does not contain a valid result, we can stop here and ‘backtrack’ to the parent node, and then try other routes. So to put it in a simple way, backtracking is DFS plus pruning. Don’t be scared about these concepts, let’s go through a few examples and you will find out that it is quite intuitive.

Leetcode Questions:

Examples

Normal strategies in the recursion function:
1. Set up an exit condition – when the exit conditions are met, jump out of the recursion.
2. If not exiting, check whether it’s qualified to go to the next level.
3. If it’s qualified to move to the next level, call recursion.
3. After returning from the next level, remember to restore the parameters to the original state.

Please note that, I’ve insert the above four steps into the codes below in comment, so you know where to put them.

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), 
find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

Note:
a. All numbers (including target) will be positive integers.
b. The solution set must not contain duplicate combinations.

Examples:
Input: candidates = [2,3,6,7], target = 7
Return: [ [7], [2,2,3] ]

This is a typical backtracking problem. To solve it, we can exhaust all possible combinations using DFS, plus pruning – once we found the sum exceeds the target, we can stop and return. Therefore, for the recursion function helper(), we need to keep track of the combination, the difference between our current sum and the target, and the index as we want to avoid duplicates by only moving forward without looking back while looping through the candidates.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ret,n = [],len(candidates)
        def helper(combination=[],remaining=target,ind=0):
            # 1. set an exit condition
            if remaining == 0:
                ret.append(combination[:])
            else:
                for i in range(ind,n):
                    # 2. check if it's possible to move to next level
                    if candidates[i] <= remaining:
                        # 3. if it's qualified, change the parameters accordingly
                        #  and call recursion
                        combination.append(candidates[i])
                        remaining -= candidates[i]
                        helper(combination,remaining,i)
                        # 4. after returning, backtrack as restoring the parameters
                        combination.pop()
                        remaining += candidates[i]
        helper()
        return ret
Combination Sum

Apart from that, when we are about to explore the further level, if we create the new parameters instead of modifying the original ones, we don’t have to restore them later. Codes are shown below:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ret,n = [],len(candidates)
        def helper(combination=[],remaining=target,ind=0):
            # 1. set an exit condition
            if remaining == 0:
                ret.append(combination[:])
            else:
                for i in range(ind,n):
                    # 2. check if it's possible to move to next level
                    if candidates[i] <= remaining:
                        # 3. if it's qualified, change the parameters accordingly
                        #  and call recursion
                        helper(combination+[candidates[i]],remaining-candidates[i],i)
        helper()
        return ret

46. Permutations

Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Similarly, we will again exhaust all possibilities – each time we will try to add one element from the input to our list, until the length of the list equals to the length of the input – unless that we found some elements are in the list already, then we will skip them.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret,n = [],len(nums)
        def helper(combin=[]):
            # 1. set an exit condition
            if len(combin) == len(nums):
                ret.append(combin[:])
            else:
                for e in nums:
                    # 2. check if it's possible to move to next level
                    if e in combin:
                        continue
                    # 3. if it's qualified, change the parameters accordingly
                    #  and call recursion
                    combin.append(e)
                    helper(combin)
                    # 4. after returning, backtrack as restoring the parameters
                    combin.pop()
        helper()
        return ret

Or, like what we do in 39. Combination Sum, we can create the new variables instead of touching the original ones.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ret = []
        def helper(remaining=nums,cur=[]):
            # 1. set an exit condition
            if remaining == []:
                ret.append(cur)
            else:
                for i in range(len(remaining)):
                    # 3. if it's qualified, change the parameters accordingly
                    #  and call recursion
                    helper(remaining[:i]+remaining[i+1:],cur+[remaining[i]])
        helper()
        return ret

References

https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments