[toc]

Backtracking

overview

  1. 纯暴力的搜索算法
  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等回溯法都可以抽象为树形结构
    • 回溯搜索的遍历过程

    在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

    如图：

    回溯算法理论基础

    注意图中，我特意举例集合大小和孩子的数量是相等的！

    回溯函数遍历过程伪代码如下：

    1
    2
    3
    4
    5
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }

    for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

    backtracking这里自己调用自己，实现递归。

    大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

    分析完过程，回溯算法模板框架如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void backtracking(参数) {
        if (终止条件) {
            存放结果;
            return;
        }

        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }

    这份模板很重要，后面做回溯法的题目都靠它了！

    如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。

77. Combinations 6/15/2024

Medium

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

1
2
3
4
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> combine( int n, int k) {
        backtracking(1, n, k);
        return res;
    }
    public void backtracking(int start, int n, int k ){
        if(temp.size() == k){
            res.add(new ArrayList<>(temp)); //！！！！！！！！！
            return ; 
        }
        for(int i =start; i <= n; i++){ //横向遍历
            temp.add(i); //纵向遍历
            backtracking(i + 1, n , k); //纵向遍历
            temp.removeLast();
            /*
            这一步的操作是在当前层级完成一次递归之后，
            将刚才加入的元素移除，以便处理当前层级的下一个元素。
            虽然这个操作本质上是在当前层级进行的，
            但它是为了准备横向遍历下一个元素。
            因此，这一步被认为是横向遍历的一部分。
            temp.removeLast() 是为了回退到当前层级的下一个状态
            */
        }
    }
}

sample code

这个遍历的范围是可以剪枝优化的，怎么优化呢？

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。

这么说有点抽象，如图所示：

77.组合4

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// pruning
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    private void combineHelper(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; n - i >=  (k - path.size()) + 1; i++){ //!!!!!!!
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

216. Combination Sum III

Medium

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

1
2
3
4
5
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();

	public List<List<Integer>> combinationSum3(int k, int n) {
		backTracking(n, k, 1, 0);
		return result;
	}

	private void backTracking(int targetSum, int k, int startIndex, int sum) {
		// 减枝
		if (sum > targetSum) {
			return;
		}

		if (path.size() == k) {
			if (sum == targetSum) result.add(new ArrayList<>(path));
			return;
		}

		// 减枝 9 - (k - path.size()) + 1
		for (int i = startIndex; (k - path.size()) <= 9 - i + 1; i++) {
			path.add(i);
			sum += i;
			backTracking(targetSum, k, i + 1, sum);
			//回溯 1 
			path.removeLast();
			//回溯 2
			sum -= i;
		}
	}
}

for循环的范围也可以剪枝，i <= 9 - (k - path.size()) + 1就可以了。

17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example 1:

1
2
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
   
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
         if (digits == null || digits.length() == 0) { //!!!!
            return res;
        } 
        backtracking(digits, 0);
        return res;
    }
    public void backtracking(String digits, int start){
        if(sb.length() == digits.length()){
            res.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start) - '0']; //!!!
        for(int i = 0 ; i < str.length() ; i++){  // Horizontal traversal !!! notice how i changes
            /* 取a,b,c*/
            sb.append(str.charAt(i)); // Vertical traversal
            /* 加a,b,c*/
            backtracking(digits, start + 1); // Vertical traversal !!!! 
            /* 集合d,e,f取字母*/
            sb.deleteCharAt(sb.length() - 1);
            /* ad (remove)-> a 
            (add)->  ae 
            (remove)-> a 
            (add)-> af
            */
        }
    }
}
  • why we need to delete the last character in each loop?

cause we only have one stringbuilder, we do all the stuff to stringbuilder.

if we dont delete anything from it, the stringbuilder would have added up all the output from each loop.

  • 例如：输入：”23”，抽象为树形结构，如图所示：

17. 电话号码的字母组合

compare this graph with the graph of previous problems, it’s slightly different

this problem, each letter is chose from different subsets. But previous problem, each number is chose from the same set.

39. Combination Sum

Medium

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

frequency

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0, 0);
        return res;
    }
    public void backtrack(int[] candidates, int target, int start, int sum){
        if(sum > target) return;
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = start ; i < candidates.length; i++){
            sum += candidates[i];
            if(sum > target) break;
            temp.add(candidates[i]);
            backtrack(candidates, target, i, sum); 
            // 不用i+1了，表示可以重复读取当前的数
            sum -= candidates[i];
            temp.remove(temp.size() - 1);
            
        }
    }
}

本题和77.组合，216.组合总和III的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

40. Combination Sum II

Medium

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, 0);
        return res;
    }
    public void backtrack(int[] candidates, int target, int start, int sum){
   
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = start ; i < candidates.length; i++){
            // if ( i > start && candidates[i] == candidates[i - 1] ) {
            //     continue;
            // }
            if(sum > target) return ; //prone
            sum += candidates[i];
            temp.add(candidates[i]);

            backtrack(candidates, target, i + 1, sum); 

            sum -= candidates[i];
            temp.remove(temp.size() - 1);


            while(i + 1 < candidates.length && candidates[i] == candidates[i+1]){
                i++;
            }
            
        }
    }
}

131. Palindrome Partitioning

Medium

Topics

Companies

Given a string s, partition s such that every

substring

of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

1
2
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>(); //!!!

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return lists;
    }

    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(deque)); //!!!!
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(s, i + 1);
            deque.removeLast();
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

graph is in the video:

https://www.bilibili.com/video/BV1c54y1e7k6/?vd_source=7cf01a4cc731f5d6335bce33c114b60c

93. Restore IP Addresses DAY28

Medium

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

1
2
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backtrack(s,0,0);
        return res;
    }
    public void backtrack(String s, int index, int point){ // index is slash
        if(point == 3){
            //check the last part, the fourth part
            if(isValid(s, index, s.length() - 1)){//left close right close
                res.add(s);
            }
            return;
        }
        for(int i = index; i < s.length(); i++){// i++是树的横向，左边划分的杠在动，划的线数量不变,因为++之前都removeLast了
            if(isValid(s, index, i)){
                s = s.substring(0, i+1)+"."+s.substring(i+1); //在str的后⾯插⼊⼀个逗点
                point++;
                backtrack(s, i + 2, point); //vertical
                point--;
                s = s.substring(0, i+1) + s.substring(i+2); // 回溯删掉逗点
            }else{
                break;
            }
        }
    } 

    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }


}

78. Subsets

Medium

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

1
2
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

1
2
Input: nums = [0]
Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets(int[] nums) {
        subsetsHelper(nums, 0);
        return result;
    }

    private void subsetsHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

90. Subsets II

Medium

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

1
2
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {

  List<List<Integer>> res = new ArrayList<>();
  LinkedList<Integer> path = new LinkedList<>();
  
  public List<List<Integer>> subsetsWithDup( int[] nums ) {
    Arrays.sort( nums );
    subsetsWithDupHelper( nums, 0 );
    return res;
  }


  private void subsetsWithDupHelper( int[] nums, int start ) {
    res.add( new ArrayList<>( path ) );

    for ( int i = start; i < nums.length; i++ ) {
        // 跳过当前树层使用过的、相同的元素
      if ( i > start && nums[i - 1] == nums[i] ) {
        continue;
      }
      path.add( nums[i] );
      subsetsWithDupHelper( nums, i + 1 );
      path.removeLast();
    }
  }

}

491. Non-decreasing Subsequences

For 90, each level, the repeated element can only show up next to each other

but for 491, repeated elements can randomly show up not necessarily next to each other that’s why we use hashset here.

Medium

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Example 1:

1
2
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    private void backTracking(int[] nums, int startIndex){
        if(path.size() >= 2)
                result.add(new ArrayList<>(path));            
        HashSet<Integer> hs = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++){
            if(path.size() > 0 && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
                continue;
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

去重做的是树层上的去重

！！！！In the provided Java code, the HashSet<Integer> hs variable is declared and instantiated within the backTracking method. Each time the backTracking method is called, a new HashSet<Integer> is created. Therefore, each invocation of the backTracking method has its own separate HashSet instance, which means that the HashSet variables do not share the same memory address across different method calls.

Each time backTracking is called, a new HashSet<Integer> hs is created.

This new HashSet is used to track elements that have already been considered in the current invocation of backTracking to avoid duplicate subsequences starting from the same index.

The HashSet helps ensure that each element in the current invocation of the loop is p

491. 递增子序列1

46. Permutations

46doesnt need to get rid of repetitive elements, but need to make sure each element is used once in each output

Medium

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

1
2
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {

    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

46.全排列

47. Permutations II

Medium

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

1
2
3
4
5
Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1]   && used[i - 1] == false) { 
                //used[i - 1] == false为了保证是树层去重
                // if used[i - 1] == true为了保证是树枝去重
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }
}

树层去重

47.全排列II1

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

在46.全排列 (opens new window)中已经详细讲解了排列问题的写法，在40.组合总和II (opens new window)、90.子集II (opens new window)中详细讲解了去重的写法。

The used array is indeed the same array throughout the recursion. This is expected and desirable because it allows each recursive call to modify and check the same state of used, ensuring consistency across different levels of recursion.