Backtracking

Problems

#	Problem	Difficulty	Hint	Tags
78	Subsets - LeetCode	Medium	Hint Draw out the recursive tree and see when we have to append the results. We backtrack by not adding the current element and moving to the next index.	#array #backtracking
39	Combination Sum - LeetCode	Medium	Hint Simple backtracking problem.	#array #backtracking
40	Combination Sum II - LeetCode	Medium	Hint How does sorting the array get rid of duplicates?	#array #backtracking
90	Subsets II - LeetCode	Medium	Hint How does sorting the array get rid of duplicates?	#array #backtracking

Backtracking is a form of Depth First Search where you incrementally try solutions that work and eliminate solutions that don't. If an option doesn't work, you backtrack by undoing the path and trying a different one.

In my mind, it is best to picture a tree like structure with different decisions at each increment. For example, in the Subsets problem, you have two decisions as you iterate through the list:

Add the current number
Don't add the current number

When you draw the try out like this, it is easy to picture how you are supposed to traverse the tree. The subsets problem is also a good template to follow for backtracking problems.

res = []
subset = []

def dfs(i):
	if i >= len(nums):
		res.append(subset.copy())
	return
	subset.append(nums[i])
	dfs(i + 1)
	subset.pop()
	dfs(i + 1)
	
dfs(0)
return res

Notice how we append a number to the list and continue down that path of the tree using depth first search. When that branch is finished, we backtrack by popping the value from the list.

The main trick to these problems in my opinion is finding the correct tree structure and backtracking method. It is usually done with a list however.

To identify if its a backtracking problem, there is usually small constraints that they are asking for all combinations of something.