• Basically a brute-force method that explores all possible paths
  • Backtracking is an Algorithm Strategy, while Recursion is more like a Algorithm Tool. Recursion powers searching problems
  • 回溯算法通常并不显式地对问题进行拆解,而是将问题看作一系列决策步骤,通过试探和Pruning (剪枝),搜索所有可能的Solution (解)
  • We can perform Pruning to improve the performance, but this will not change the overall worst case
  • Iterative Recursion doesn’t work well to implement this algorithm, stick to Recursion - backtracking allows us to implicitly create multiple nested for-loops until we find the desired answer

Tips in solving Leetcode

Pruning (剪枝)

  • When in finding sum questions, sort the given Array before backtracking, then we can skip the rest of the loops if +the next element is bigger

Remove Duplicates in Combination

  • Sort the given set
  • At each level, we skip the elements that have the same value as the previous element
// In the primary function
// In Backtracking function
for (start = start; start<nums.length; start++) {
	// ...
	while(start < nums.length-1 && nums[start]==nums[start+1]) start++;

2 Ways to Remove Duplicates in Permutation (排列)

  1. Use a Hash Set/Array to remove duplicates at each level, given the element value is small
// Without the need to sort the given array in the primary function
// In Backtracking function
boolean[] duplicates = new boolean[21];
for (int i=0; i<nums.length; i++) { 
	if (duplicates[nums[i]+10]) continue;
	duplicates[nums[i]+10] = true;
	// ...
  1. Sort the given Array, then remove duplicates by checking if the previous element is same as current element && isn’t used which means the previous element with the same value can be used, resulting in a duplicated Permutation (排列)
// In the primary function
// In Backtracking function
if (i>0 && nums[i-1]==nums[i] && visited[i-1]==false) continue;

Leetcode Questions



Single Set

Multiple Sets

Partition (分割)


  • Basically Combination without re-using the same element

Subset (子集)

Maintain Given Order

Permutation (排列)

Without Duplicates

With Duplicates

Chessboard Problem


Solution (解)

Constraint (约束条件)

State (状态)

  • Represents the problem at any point of the time, including the choices made

Attempt (尝试)

Backtracking (回退)

  • Removing the previous choice made & return to the previous State (状态)

Pruning (剪枝)

  • Based on Constraint (约束条件), Avoid exploring some paths fully when we know there isn’t a point to explore nodes on the rest of the path or other paths, to save on the computation
  • For example, when the question says the Solution (解) must contains a certain number of nodes, we can terminate Attempt (尝试) if we see there is no way to get to that number of nodes