Back Tracking🌼

在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

回溯法模板

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

这里给出Carl总结的回溯算法模板。

在讲二叉树的递归中我们说了递归三部曲，这里我再给大家列出回溯三部曲。

  • 回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下：

1
void backtracking(参数)
  • 回溯函数终止条件

既然是树形结构，那么我们在讲解二叉树的递归的时候，就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

1
2
3
4
if (终止条件) {
    存放结果;
    return;
}
  • 回溯搜索的遍历过程

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

如图：

回溯算法理论基础

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

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

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(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

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

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

Generally, every constraint satisfaction problem which has clear and well-defined constraints on any objective solution, that incrementally builds candidate to the solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution, can be solved by Backtracking. However, most of the problems that are discussed, can be solved using other known algorithms like Dynamic Programming or Greedy Algorithms in logarithmic, linear, linear-logarithmic time complexity in order of input size, and therefore, outshine the backtracking algorithm in every respect (since backtracking algorithms are generally exponential in both time and space). However, a few problems still remain, that only have backtracking algorithms to solve them until now.

linkedList VS. ArrayList

https://www.geeksforgeeks.org/arraylist-vs-linkedlist-java/

ArrayList provides constant time for search operation, so it is better to use ArrayList if searching is more frequent operation than add and remove operation.

The LinkedList provides constant time for add and remove operations. So it is better to use LinkedList for manipulation.

LinkedList:

  1. Adding Elements:
    • addFirst(element): Adds an element to the beginning of the list.
    • addLast(element): Adds an element to the end of the list.
    • add(index, element): Adds an element at the specified index.
  2. Removing Elements:
    • removeFirst(): Removes and returns the first element.
    • removeLast(): Removes and returns the last element.
    • remove(index): Removes the element at the specified index.
  3. Accessing Elements:
    • get(index): Retrieves the element at the specified index.
    • linkedList.set(i, newValue);
  4. Iterating:
    • Iterating through elements using an iterator or enhanced for loop.
  5. Size:
    • size(): Returns the number of elements in the list.

ArrayList:

  1. Adding Elements:
    • add(element): Adds an element to the end of the list.
    • add(index, element): Adds an element at the specified index.
  2. Removing Elements:
    • remove(index): Removes the element at the specified index.
    • removeRange(fromIndex, toIndex): Removes elements within the specified range.
  3. Accessing Elements:
    • get(index): Retrieves the element at the specified index.
    • set(index, element): Replaces the element at the specified index.
  4. Iterating:
    • Iterating through elements using an iterator or enhanced for loop.
  5. Size:
    • size(): Returns the number of elements in the list.

ArrayList Specific:

  1. Dynamic Sizing:
    • The underlying array dynamically grows as elements are added, reducing the need for manual resizing.
  2. Random Access:
    • Provides fast O(1) random access to elements by index.
  3. Insertion/Deletion Trade-Off:
    • Insertions and deletions at the beginning/middle of the list are slower (O(n)) due to shifting elements.

LinkedList Specific:

  1. Insertion/Deletion:
    • Offers fast O(1) insertion and deletion at the beginning and end of the list.
    • Mid-list insertions/deletions are slower (O(n)) due to traversal.
  2. Memory Overhead:
    • Uses more memory due to storing both elements and references/pointers.
  3. No Random Access:
    • Accessing elements by index is slower (O(n)) since traversal is required.

Both LinkedList and ArrayList provide similar APIs for common operations like adding, removing, accessing, and iterating through elements. The choice between them depends on your specific use case and the operations you’ll perform most frequently.

77. Combinations 排列问题

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
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
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {  
        seek(n,k,1);
        return  res;
    }

     public void seek(int n, int k, int start) {
         if(path.size() == k ){
             res.add(new ArrayList<>(path));
             return;
         }
         for(int i = start; i <= n; i++){
             path.add(i); //like put in the element 1
             seek(n,k, i+1); // recursive like 从1以后的元素遍历，加进去
             path.removeLast();  // backtrack 比如说加了1，2 进去然后把2退出来，再加3进去成为1，3
         }
     }
}

why res.add(new ArrayList<>(path)); instead of using res.add(path).

你的 path 是一个 LinkedList，用于存储当前正在构建的组合。当你找到一个符合条件的组合时，你想把这个组合加入到 res 中，然后继续寻找其他的组合。

问题在于，LinkedList 是一个可变的数据结构，也就是说，当你向 path 中添加或删除元素时，path 的内容会发生变化。

如果你直接将 path 加入到 res 中，实际上你只是将 path 对象的引用加入到了 res 中，而不是 path 的一个拷贝。这意味着，如果之后你继续修改 path，那么 res 中保存的组合也会随之改变，这样会导致 res 中的结果不正确。

所以，为了避免这个问题，你需要在将 path 加入到 res 中之前，先创建一个 path 的拷贝，然后再将拷贝加入到 res 中。这样，即使之后 path 发生变化，res 中保存的组合仍然保持不变。

when you add path directly to res, you’re not adding a copy of path, you’re adding a reference to the same LinkedList object. During backtracking, as you remove elements from path, those changes will also reflect in the lists already added to res. This leads to incorrect results because the contents of path are changing during the exploration of different combinations.

  • 回溯函数终止条件

什么时候到达所谓的叶子节点了呢？

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

如图红色部分：

77.组合3

此时用result二维数组，把path保存起来，并终止本层递归。

所以终止条件代码如下：

1
2
3
4
if (path.size() == k) {
    result.push_back(path);
    return;
}
  • 单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

77.组合1

如此我们才遍历完图中的这棵树。

for循环每次从startIndex开始遍历，然后用path保存取到的节点i。

代码如下：

1
2
3
4
5
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。

backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。

77. Combinations 减枝pruning

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0077.%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96.md

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
    private void combineHelper(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){  //!!!!!!!
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
    
    
    
//my version


class Solution {
    List<List<Integer>> res =  new ArrayList<>();
    
    public List<List<Integer>> combine(int n, int k) {
        if(n == 0 || k == 0) return res;
        List<Integer> temp = new LinkedList<>();
        backtrack(n, k, 1, temp);
        return res;
    }
    void backtrack(int n, int  k, int start, List<Integer> temp ){
        if(temp.size() == k){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = start; i <= n ; i++){
             if(k - temp.size() <= n - i + 1 ){
                temp.add(i);
       
                 backtrack(n, k, i + 1, temp);
 
                temp.removeLast( );
            }
        }
    }
}

path.size() ： 已经找的个数
k-path.size() ：还需找的个数
【x, n】的数组长度起码应该是k-path.size()才有继续搜索的可能， 那么就有 n-x+1 = k-path.size() ， 解方程得 x = n+1 - (k-path.size()), 而且这个x是可以作为起点往下搜的 也就是for(i = s; i<=x; i++) 这里的x是可以取到的

216. Combination Sum III

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
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
class Solution {
    public List<List<Integer>>res = new ArrayList<>();
    public LinkedList<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        seek(k, n , 1);
        return res;
    }
    public void seek(int k, int n, int start){
        if(path.size() == k){
            int sum = 0;
            for(int element: path){
                sum += element;
            }
            if(sum == n){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i = start; i <= 9; i++){
            path.add(i);
            seek(k,n, i+1);  // notice it's i+1 here not start +1
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// pruning!!! better version

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; i <= 9 - (k - path.size()) + 1; i++) {
			path.add(i);
			sum += i;
			backTracking(targetSum, k, i + 1, sum);
			//回溯
			path.removeLast();
			//回溯
			sum -= i;
		}
	}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    public List<String> res = new ArrayList<String>();
    public StringBuilder temp = new StringBuilder();
    public String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //!!!!!!!!!!

    public List<String> letterCombinations(String digits) {
        if( digits.isEmpty()) return res;
        /*
        notice:
        	not return null
        	not digits == null
        */
        seek(digits, 0);
        return res;
    }
    public void seek(String digits, int num){ // num stands for which digit we are processing 遍历到哪一个数字了
        
        int len = digits.length();
        if(len == num){
        // you can also say-> if(len == temp.length()){
            res.add(temp.toString());
            return;
        }
        int digit = digits.charAt(num) - '0';
        String str = dict[digit]; // current digit's letters 
        for(int i = 0; i < str.length(); i++){
            temp.append(str.charAt(i));
            seek(digits, num+1); // append next num's letter
            temp.deleteCharAt(temp.length() - 1);
        }

    }
}

//second try:(chaotic) use string array could make code look better
class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")){
            return res;
        }  
        int[] digit = new int[digits.length()];
        for(int i = 0 ; i < digits.length(); i++){
            digit[i] = digits.charAt(i) - '0';
        }
        com(digit, 0);
        return res;
    }
    void com(int[] digit, int start){
        if(temp.length() == digit.length){
            res.add(temp.toString());
            return;
        }

        for(int i = start; i < digit.length; i++){
            int order = 3;
            if(digit[i] == 7 || digit[i] == 9) order = 4;

            int base;
                if(digit[i] < 8){
                    base =  (digit[i] - 2)*3;
                }else if( digit[i] == 8){
                    base = 19;
                }else{
                    base = 22;
                }
            
            for(int j = 0 ; j < order; j++){
                
               temp.append((char)('a' + j + base ));
               com(digit, i + 1);
               temp.deleteCharAt(temp.length() - 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
// 版本二
class Solution {
private:
        const string letterMap[10] = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
        };
public:
    vector<string> result;
    void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            getCombinations(digits, index + 1, s + letters[i]);  // 注意这里的不同
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        getCombinations(digits, 0, "");
        return result;

    }
};

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.

Example 2:

1
2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    public List<List<Integer>> res =  new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        seek(candidates, target, 0, 0);
        return res;
    }
    public void seek(int[] candidates, int target, int index, int sum){
        if(sum > target)
        return;
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;  //!!!! 我用break 也通过了，但是这里我觉得用return更好想   
            //这里不可以用continue，如果是continue的话层序遍历还会继续
            //这里用return 不用 continue,终止的是这个深度上的检索
        } 
        for(int i = index; i < candidates.length; i++){
            temp.add(candidates[i]);  //notice here is i not index
            sum += candidates[i];
            seek(candidates, target, i, sum);
            temp.remove(temp.size() - 1);
            sum -= candidates[i];
        }
    }
}




pruning:
// 剪枝优化
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
}

//second try:
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        cal(candidates, target, 0,0);
        return res;
    }
    public void cal(int[] candidates, int target, int index, int sum){
        if(index > candidates.length || sum > target){
            return;
        }
         
        for(int i = index ; i < candidates.length; i++){
            if(sum == target){
                res.add(new LinkedList<>(temp));
                break;
            }
            
                temp.add(candidates[i]);
                sum += candidates[i];
                cal(candidates, target, i, sum);
                sum-= candidates[i];
                temp.removeLast();
            
        }
    }
}

40. Combination Sum II

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.

这道题强调了candidates里面有重复的元素，我们需要去重

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        seek(candidates, target, 0, 0);
        return res;
    }
    public void seek(int[] candidates, int target, int index, int sum){
        if(sum > target) return;
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index; i < candidates.length; i++){
            if(i >  index && candidates[i-1] == candidates[i]) !!!!!!!!!!!! //树层逻辑， 横向检查
            continue;
            temp.add(candidates[i]);
            sum += candidates[i];
            seek(candidates, target, i + 1, sum);
            temp.remove(temp.size() - 1);
            sum -= candidates[i];
        }
    }
}


//second try:
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        cal(candidates, target, 0, 0);
        return res;
    }
    public void cal(int[] candidates, int target, int index, int sum){
        if( sum > target) return;
        if(sum == target){
                res.add(new LinkedList<>(temp));
                return;
        }
        for(int i = index; i < candidates.length; i++){
            if ( i > index && candidates[i] == candidates[i - 1] ) {
        continue;
      }
      or: while(i > index && candidates[i] == candidates[i - 1]) i++;
      wrong: while(i + 1 < candidates.length && candidates[i] == candidates[i+1] ) i++; //要和前面比不能和后面比。
      
      
            temp.add(candidates[i]);
            sum += candidates[i];
            cal(candidates, target, i + 1, sum);
            temp.removeLast();
            sum -= candidates[i];
            //while(i + 1 < candidates.length && candidates[i] == candidates[i+1] ) i++;
        }
    }
}

树层（横向）上不能重复，

树枝（纵向）上可以重复。

if(i > index && candidates[i-1] == candidates[i])

这里如果想不明白的话，其实这句话等同于

if( i != index && candidates[i-1] == candidates[i]) continue; 从第二个开始去重

—-> 就是重复出现的只保留最左侧的一支树枝，其他的就去重
比如说 【1， 1， 1， 1， 2】 求和是3， 只保留最左侧的 1->1->1这样子一支树

131. Palindrome Partitioning分割问题

Medium

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public List<List<String>> res = new ArrayList<>();
    public LinkedList<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        seek(s,0);
        return res;
    }
    public boolean pal(String s, int left, int right){
        for(int i = left; i < right; i ++){
            if(s.charAt(i) == s.charAt(right)){
                right --;
            }else{
                return false;
            }
        }
        return true;
    }
    public void seek(String s, int index){
        if(index >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i < s.length(); i++){ 
        //i++是树的横向，左边划分的杠在动，划的线数量不变,因为++之前都removeLast了
            if(pal(s,index, i)){
                String str = s.substring(index, i+1);
                // for substring, left is closed but the right is open
                path.add(str);
            }else{
                continue; //注意这里是continue不是return;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                
                //如果这里是return, 相当于层序遍历直接就终止了。
            } 
            seek(s, i+1); //树的纵向, i+1是右边的划杠在动，划的线增多
            path.removeLast();
        }
    }
}

//对比39：
class Solution {
    public List<List<Integer>> res =  new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        seek(candidates, target, 0, 0);
        return res;
    }
    public void seek(int[] candidates, int target, int index, int sum){
        if(sum > target)
        return;
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;  //!!!! 我用break 也通过了，但是这里我觉得用return更好想   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            //这里不可以用continue，如果是continue的话层序遍历还会继续
            //这里用return 不用 continue,终止的是这个深度上的检索
        } 
        for(int i = index; i < candidates.length; i++){
            temp.add(candidates[i]);  //notice here is i not index
            sum += candidates[i];
            seek(candidates, target, i, sum);
            temp.remove(temp.size() - 1);
            sum -= candidates[i];
        }
    }
}

131.分割回文串

视频讲解看93的，讲的更清楚：https://www.bilibili.com/video/BV1XP4y1U73i/?vd_source=7cf01a4cc731f5d6335bce33c114b60c

93. Restore IP Addresses

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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);
                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;
    }


}






//second try
class Solution {
    List<String> res = new LinkedList<>();
    //StringBuilder temp = new StringBuilder();
    int len;
    public List<String> restoreIpAddresses(String s) {
        len= s.length();
        sort(s, 0);
        return res;
    }
    public void sort(String s, int index){
        if(s.length() == len + 3){
            if(check(s, index, s.length() - 1))
                res.add(s);
            return;
        }

        for(int i = index; i < s.length(); i++){
            if( check(s, index, i)){
                s = s.substring(0, i+1) + "." + s.substring(i+1);
                sort(s, i + 2);
                s = s.substring(0, i+1) + s.substring(i + 2);

            }else{
                break;
            }
        }
    }
    // public boolean check(String s , int start, int end){
    //      if (start > end) {
    //         return false;
    //     }
    //     if(s.charAt(start) == '0' && start != end) return false;
    //     //if(s!="" && Integer.parseInt(s.substring(start,end)) > 255) return false;

    //     String substring = s.substring(start, end);
    
    //     if (!substring.isEmpty()) {
    //     int intValue = Integer.parseInt(substring);
    //     if (intValue > 255)  return false;
    //     }

    //     for(int i = start ; i < end; i++){
    //         if(s.charAt(i) > '9' || s.charAt(i) < '0') 
    //             return false;
    //     }
    //     return true;
    // }

         private Boolean check(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;
    }



}

s.substring(i + 1) expression suggests that you’re extracting a substring from the string s, starting from the index i + 1 and continuing until the end of the string.

93.复原IP地址

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]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>(temp)); // 加上空子集
        backtrack(nums, 0);
        return res;
    }
    public void backtrack(int[] nums, int index){
        if(index >= nums.length) return;
        
        for(int i = index; i < nums.length; i++){
            //res.add(new ArrayList<>(temp));
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            backtrack(nums, i + 1);
            temp.removeLast();
        }

    }
}

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

78.子集

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

90. Subsets II

Medium

Companies

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
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res.add(temp);
        Arrays.sort(nums);
        backTrack(nums, 0);
        return res;
    }
    public void backTrack(int[] nums, int index){
        if(index >= nums.length) return;
        for(int i = index; i < nums.length; i++){
            if(i > index && nums[i] == nums[i-1]){
               continue;  //最好把这种需要退出的情况写在前面
            }else{
                temp.add(nums[i]);
                res.add(new ArrayList<>(temp));
                backTrack(nums, i+1);
                temp.removeLast();
            }
            
        }
    }
}


WRONG VERSION:   ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
    public void backTrack(int[] nums, int index){
        if(index >= nums.length) return;
        for(int i = index; i < nums.length; i++){
            if(i > index && nums[i] != nums[i-1]){
                temp.add(nums[i]);
                res.add(new ArrayList<>(temp));
                backTrack(nums, i+1);
                temp.removeLast();
            }else{
                continue;
            }
            
        }
    }
    
// second try:
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        res.add(new LinkedList<>());
        find(nums, 0);
        return res;
    }
    public void find(int[] nums, int index){
        if(index >= nums.length) return;
        for(int i = index; i < nums.length; i++){
            if( i > index && i  < nums.length && nums[i] == nums[i - 1]) continue;
            temp.add(nums[i]);
            res.add(new LinkedList<>(temp));
            //if( i + 1< nums.length && nums[i] == nums[i + 1]) continue; !!!!!!!!!!!!注意这个放的位置
            find(nums, i+1);
            temp.removeLast();
        }
    }
}

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        res.add(new LinkedList<>());
        find(nums, 0);
        return res;
    }
    public void find(int[] nums, int index){
        if(index >= nums.length) return;
        for(int i = index; i < nums.length; i++){
            // if ( i > start && nums[i - 1] == nums[i] ) {
            //     continue;
            // }
            while (i > index && i < nums.length && nums[i] == nums[i - 1]) {
                i++;
            }
            if(i >= nums.length) 
            //i = nums.length -1 ; 这样的话最后一个元素会多算一次
            break;

            temp.add(nums[i]);
            res.add(new LinkedList<>(temp));
            
            //if( i + 1< nums.length && nums[i] == nums[i + 1]) continue;
            find(nums, i+1);
            temp.removeLast();
        }
    }
}

90.子集II

从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

491. Non-decreasing Subsequences

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
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
22
23
24
25
26
27
28
29
30
31
class Solution {

    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtrack(nums, 0);
        return res;
    }
    public void backtrack(int[] nums, int index){
        // if(nums.length == index){
        //     return;
        // }  if you add this, the result is wrong, should put this after if(temp.size() > 1) statement
        if(temp.size() > 1){
            res.add(new ArrayList<>(temp));
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = index; i < nums.length; i++){
           if(!temp.isEmpty() && nums[i] < temp.getLast()){
               continue;
           }
           if(map.getOrDefault(nums[i], 0) == 1){
               continue;
           }
           map.put(nums[i], 1);
           temp.add(nums[i]);
           backtrack(nums, i+1);
           temp.removeLast();
        
        }
    }
}

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

非常非常详细！

46. Permutations 排列问题

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
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) return res;
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }
    public void backtrack(int[] nums){
        if(nums.length == temp.size()) {
            res.add(new ArrayList<>(temp));
            return;
        }
       // cant use hash map here   HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i <nums.length; i++){
            if(used[i]) continue;
            used[i] = true;
            temp.add(nums[i]);
            backtrack(nums);
            temp.removeLast();
            used[i] = false;
        }
    }
}

46.全排列

这里和77.组合问题、131.切割问题和78.子集问题最大的不同就是for循环里不用startIndex了。

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

！！！！！！！！！！！！ used数组是用来标记图里面，箭头上写的取的几。！！！！！！！！！

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums){
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }
    public void backtrack(int[] nums){
        if(nums.length == temp.size()){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i-1] && used[i - 1] == false) continue; //!!!!!notice  used[i - 1] == false !!!
            if(used[i] == true) continue;
            used[i] = true;
            temp.add(nums[i]);
            backtrack(nums);
            used[i] = false;
            temp.removeLast();
        }
    }
}

// use linkedlist to see if it contains duplicate elements
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();
    HashSet<Integer> set = new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
      
        int[] used = new int[nums.length];
        find(nums, used);
        return res;
    }
    public void find(int[] nums, int[] used){
        if(temp.size() == nums.length){
            if(!res.contains(temp))
            res.add(new LinkedList<>(temp));
            return;
        }
        
        for(int i = 0 ; i < nums.length; i++){
            if( used[i] == 1) continue;
                temp.add(nums[i]);
                used[i] = 1;
                find(nums, used);
                temp.remove(temp.size() - 1);
                used[i] = 0;
        
        }
    }
}

我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程

中, 我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

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

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

拓展

这道题其实还是用了我们之前讲过的去重思路，但有意思的是，去重的代码中，这么写：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

和这么写：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

都是可以的，这也是很多同学做这道题目困惑的地方，知道used[i - 1] == false也行而used[i - 1] == true也行，但是就想不明白为啥。

所以我通过举[1,1,1]的例子，把这两个去重的逻辑分别抽象成树形结构，大家可以一目了然：为什么两种写法都可以以及哪一种效率更高！

这里可能大家又有疑惑，既然 used[i - 1] == false也行而used[i - 1] == true也行，那为什么还要写这个条件呢？

直接这样写 不就完事了？

1
2
3
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

其实并不行，一定要加上 used[i - 1] == false或者used[i - 1] == true，因为 used[i - 1] 要一直是 true 或者一直是false 才可以，而不是 一会是true 一会又是false。 所以这个条件要写上。

okay if you cant understand here then just check the website

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：

47.全排列II2

树枝上去重（used[i - 1] == true）的树型结构如下：

47.全排列II3

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

去重（一些错误写法的提醒）

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E5%8E%BB%E9%87%8D%E9%97%AE%E9%A2%98%E7%9A%84%E5%8F%A6%E4%B8%80%E7%A7%8D%E5%86%99%E6%B3%95.md

51. N-Queens

Hard

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

img

1
2
3
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
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
50
51
52
53
54
55
56
57
class Solution {
    public List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');    !!!!!!!
        }
        backtrack(board, n , 0);
        return res;
    }
    public void backtrack(char[][] board,int n, int row){
        if(row == n){ //走到叶子节点，那一定是合法的
            res.add(Array2List(board));
            return;
        }
        for(int i = 0; i<n; i++){
            if(check(board,n,row,i)){
                board[row][i] = 'Q';
                backtrack(board, n, row + 1);
                board[row][i] = '.';
            }
        }
    }

    public List Array2List(char[][] chessboard) {!!!!!
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));  !!!!!
        }
        return list;
    }

    public boolean check(char[][] chessboard, int n, int row, int col) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row, j=col; i>=0 && j>=0; i--, j--) {!!!!!!
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row, j=col; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
wrong version:

    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {

            for(char cc :  c)
            {
                list.add(Character.toString(cc));
            }
        }
        return list;
    }

Output

[[“.”,”Q”,”.”,”.”,”.”,”.”,”.”,”Q”,”Q”,”.”,”.”,”.”,”.”,”.”,”Q”,”.”],[“.”,”.”,”Q”,”.”,”Q”,”.”,”.”,”.”,”.”,”.”,”.”,”Q”,”.”,”Q”,”.”,”.”]]

Expected

[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]

  1. Using Arrays.fill():
1
2
3
javaCopy codefor (char[] c : board) {
    Arrays.fill(c, '.');
}

In this approach, you are using the Arrays.fill() method to fill each row of the 2D array board with the character '.'. This method directly modifies the array elements in place, replacing the characters within each subarray with '.'.

  1. Using nested loops:
1
2
3
4
5
javaCopy codefor (char[] c : board) {
    for (char cc : c) {
        cc = '.';
    }
}

In this approach, you are using nested loops to iterate through each row (char[] c) and then iterating through each character (char cc) within that row. However, the assignment cc = '.'; only updates the value of the loop variable cc, which does not have any effect on the actual characters stored in the board array. This means that the characters within the board array remain unchanged.

The key difference is that the first approach (Arrays.fill()) directly modifies the array elements, while the second approach (nested loops) only modifies the loop variables without affecting the array contents.

To achieve the same result as the Arrays.fill() approach, you would need to use the index to update the characters within the board array:

1
2
3
javaCopy codefor (int i = 0; i < board.length; i++) {
    Arrays.fill(board[i], '.');
}

This way, you are directly modifying the characters in the board array using the indices of the rows and columns.

这样也可以：

1
2
3
4
5
for(int i = 0; i < n; i++){
    for(int j = 0 ; j < n; j++){
        board[i][j] = '.';
    }
}

[toc]