🌲

BackTracking

BackTracking is an elegant version of brute force, used to solve problem like

Combination

Permutation

Subgroup

String Cutting (Partition)

N Queens

BackTracking can be modeled as traversing a N-branch tree.


def backtracking(**args):
	if (...): # ending condition
		# save results
		return
				
	for (...): # select children of this level
		# handle node
		backtracking(...) # recursion
		# cancel operation

E.g. For combination


def Solution(iList, k): # n choose k from iList
	def backtracking(startIndex, path, result):
		if len(path) == k:
			result.append(path)
				return
		for i in range(startIndex, n):
			backtracking(i + 1, path + [iList[i]], result)
	result = []
	backtracking(0, [], result)
	return result

Remarks:

If order doesn’t matter (we do not want [a, b, c] & [c, b, a] together), use startIndex (combination, partition, subgroup). Otherwise, use range(0, n) (permutation)

Problems:

Combination

Time: , Space:
77: Combinations
216: Combination Sum III
17: Letter Combinations of a Phone Number
40: Combination Sum II (No Repeat among branches)

Partition

Subgroup

Time: , Space:
78: Subsets
90: Subsets II (No Repeat among branches)
491: Non-decreasing Subsequences (No Repeat in the same level of one branch)

Permutation

Other Applications

Loading Comments...