LeetCode回溯算法章节

LeetCode回溯算法章节

回溯模板

1
2
3
4
5
6
7
8
9
10
void backtrace(参数){
	if(终止条件)
		return;
	for(每层中的元素)
	{
		存入结果
		backtrace();调用回溯
		删除存入的结果，回溯
	}
}

组合

[组合](77. 组合 - 力扣（LeetCode）)

回溯

从[1,N]中找到凑成K个数的所有组合，将[i,N]（i=1,2,3…N）看做一棵树的不同结点，每取出一个数就把剩下的数看做该结点的子结点，叶子结点则为符合要求的结果。因此，for循环中的是不断取出一个数进入递归，结束递归后删除，再递增取下一个数，直到遇到结束条件退出递归。即for循环会遍历[1,N]中所有的元素，每添加一个元素进入数组就进入一层递归，但进入递归后若符合终止条件则会跳出，避免了N次方的时间复杂度。也相当于枚举法，但会及时止损

  1. 确定回溯终止条件

    1
    2
    3
    4
    5
    if(vec.size()==k)
    {
    	res.push_back(vec);
    	return;
    }

    当数组大小符合要求时，也就是遇到了叶子结点，这一次递归就终止，并更新结果集

  2. 确定回溯返回值

    1
    2
    3
    4
    void search(int n,int k,vector<vector<int>>& res,vector<int>& vec,int start)
    {
    	不需要返回值
    }

  3. 确定单层逻辑

    1
    2
    3
    4
    5
    6
    for(int i = start;i<=n;i++)
    {
    	vec.push(i);
    	search(n,k,res,vec,start+1);
    	vec.pop_back();
    }

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void search(int n, int k, vector<vector<int>>& res, vector<int>& vec, int start)
    {
        if (vec.size() == k)
        {
            res.push_back(vec);
            return;
        }
        for (int i = start; i <= n; ++i)
        {
            vec.push_back(i);
            search(n, k, res, vec, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> vec;
        search(n, k, res, vec, 1);
        return res;
    }
};

回溯优化

在回溯算法当中，由于是回溯的本质就是枚举，对枚举的优化只在于剪枝，通过给定限定条件减少无必要的递归，本题也同样如此，以上版本中将start赋予到了i，却并没有考虑到start的位置要求，在某些分支中，start过于太大，导致剩下的元素不能满足k的数量要求，因此，可以对回溯进行剪枝优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void search(int n, int k, vector<vector<int>>& res, vector<int>& vec, int start)
    {
        if (vec.size() == k)
        {
            res.push_back(vec);
            return;
        }
        for (int i = start; i <= n - (k - vec.size()) + 1; ++i)
        {
            vec.push_back(i);
            search(n, k, res, vec, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> vec;
        search(n, k, res, vec, 1);
        return res;
    }
};

剪枝的原因在于i不必从过于大的start中取值，因此将对for循环中i的循环结束语句修改，从进入递归之前剪枝

总结

回溯算法难点在于将题意转换成树形结构，对于树形结构可以更好的理解回溯，以及剪枝的操作

组合总和III

回溯

题目思路类似于上一题，只不过将取值范围固定在1~9之间，其余都一样

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void traceback(int k, int n, vector<vector<int>>& res, vector<int>& vec, int index)
    {
        if (vec.size() == k)
        {
            if (accumulate(vec.begin(), vec.end(), 0) == n)
                res.push_back(vec);
            return;
        }
        for (int i = index; i <= 9; i++)
        {
            vec.push_back(i);
            traceback(k, n, res, vec, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> vec;
        traceback(k, n, res, vec, 1);
        return res;
    }
};

回溯优化

在以上版本代码中，容易看出需要优化的地方在于取值的范围是递增的，一旦有满足总和的vec数组，后续的遍历中的数组总和只会更大，因此可以忽略掉后续的遍历。类似地，同样在递归进入条件判断语句中增加限制，考虑到是用数组总和来做判断是否需要剪枝，则增加一个形参sum表示当前vec数组的总和

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:
    void traceback(int k, int n, vector<vector<int>>& res, vector<int>& vec, int index, int& sum)
    {
        if (vec.size() == k)
        {
            if (sum == n)
                res.push_back(vec);
            return;
        }
        for (int i = index; i <= 9 && (n - sum) >= i; i++)
        {
            sum += i;
            vec.push_back(i);
            traceback(k, n, res, vec, i + 1, sum);
            sum -= i;
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> vec;
        int sum = 0;
        traceback(k, n, res, vec, 1, sum);
        return res;
    }
};

总结

在回溯法中，如果想要不重复地访问元素，则需要traceback(k,n,res,vec,i+1)而不是traceback(k,n,res,vec,index+1)，后者会在i遍历时，与index+1有重复值，且重复值只从2开始

本题是与上题相同的回溯思路，但不同的剪枝思路。

电话号码的字母组合

[电话号码的字母组合](17. 电话号码的字母组合 - 力扣（LeetCode）)

回溯

与前些题目不同的是，没有直接能获取到要进入递归的范围，即递归树的结点，需要借助容器来获取数值范围，这里使用数组保存0~9所分别对应的字母。

1
2
3
4
5
6
7
8
9
10
11
vector<vector<string>> hashmap{
    {},
    {},
{"a","b","c"},
{"d","e","f"},
{"g","h","i"},
{"j","k","l"},
{"m","n","o"},
{"p","q","r","s"},
{"t","u","v"},
{"w","x","y","z"} };

这里保存0,1两个空数组是为了方便索引访问直接对应

  1. 确定递归结束条件

    1
    2
    3
    4
    5
    if(digits.size()==str.size())
    {
    	res.push_back(str);
    	return;
    }

  2. 确定递归返回值

    1
    void traceback(vector<string>& res, string& str,const string &digits,int index);

  3. 确定单层逻辑

    1
    2
    3
    4
    5
    6
    for(int i = 0;i<hashmap[digit].size();i++)
            {
                str += hashmap[digit][i];
                traceback(res,str,digits,index+1);
                str.pop_back();
            }

整体代码如下

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 {
public:
    vector<vector<string>> hashmap{
        {},
        {},
    {"a","b","c"},
    {"d","e","f"},
    {"g","h","i"},
    {"j","k","l"},
    {"m","n","o"},
    {"p","q","r","s"},
    {"t","u","v"},
    {"w","x","y","z"}};

    void traceback(vector<string>& res,string& str,const string &digits,int index)
    {
        if(str.size()==digits.size())
        {
            res.push_back(str);
            return;
        }
        int digit = digits[index] - '0';

        for(int i = 0;i<hashmap[digit].size();i++)
        {
            str += hashmap[digit][i];
            traceback(res,str,digits,index+1);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string str;

        if(digits.empty())  return res;
        traceback(res,str,digits,0);        
        return res;
    }
};

总结

由回溯过程可知，这个版本的回溯代码不需要剪枝优化。

在本题中，传入递归函数的index形参用来获取digits中的下一位数字，保证每次for循环的都是不同进位上的数字，也是这道题的最大变化点。并且不需要传入其余参数用于表示开始遍历的结点索引，因为需要遍历的是对应数字上的所有字母

组合总和

[组合总和](39. 组合总和 - 力扣（LeetCode）)

回溯

这道题给定一个数组和目标值，要求从数组中找到不限数量的数组元素，令其和等于目标值，并且能够重复用数组中的元素。最大的不同点在于能够重复使用数组元素，首先能想到的就是不需要index形参，不能让递归每次都从下一个元素开始遍历。

  1. 确定递归结束条件

    1
    2
    3
    4
    5
    if(target == sum)
    {
    	res.push_back(vec);
    	return;
    }

    容易想到只要让当前数组的和等于目标值即可结束该层递归，即到达叶子结点。但是这样就会导致了死循环，因为如果一旦数组和大于目标值，则递归永远不会退出。因此需要加上对sum值的限制（在进入递归前判断）

  2. 确定递归返回值

    1
    void traceback(vector<int>& candidates, vector<vector<int>> &res,vector<int> &vec,int target,int &sum,int startindex)

  3. 确定单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    for (int i = startindex; i < candidates.size() && target > sum; i++)
            {
                vec.push_back(candidates[i]);
                sum += candidates[i];
                traceback(candidates, res, vec, target, sum, i);
                sum -= candidates[i];
                vec.pop_back();
            }

    在这，startindex作为每次遍历时开始的索引下标，与[III](# 组合总和III)不同，传入到下一次递归的是i而不是i+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
class Solution {
public:
    void traceback(vector<int>& candidates, vector<vector<int>>& res, vector<int>& vec, int target, int& sum, int startindex)
    {
        if (sum == target)
        {
            res.push_back(vec);
            return;
        }
        for (int i = startindex; i < candidates.size() && target 》 sum; i++)
        {
            vec.push_back(candidates[i]);
            sum += candidates[i];
            traceback(candidates, res, vec, target, sum, i);
            sum -= candidates[i];
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> vec;
        int sum = 0;
        traceback(candidates, res, vec, target, sum, 0);
        return res;
    }
};

回溯优化

可以想到，如同[III](# 组合总和III)，剪枝优化的思路在于当数组递增时，一旦有满足目标值的数组元素，往后的元素再进入递归，vec数组的和都会大于目标值，因此可以剪掉，所以先给数组进行排序，然后在递归进入前加以条件的限制

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:
    void traceback(vector<int>& candidates, vector<vector<int>>& res, vector<int>& vec, int target, int& sum, int startindex)
    {
        if (sum == target)
        {
            res.push_back(vec);
            return;
        }
        for (int i = startindex; i < candidates.size() && (target - sum) >= candidates[i]; i++)
        {
            vec.push_back(candidates[i]);
            sum += candidates[i];
            traceback(candidates, res, vec, target, sum, i);
            sum -= candidates[i];
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> vec;
        sort(candidates.begin(), candidates.end());
        int sum = 0;
        traceback(candidates, res, vec, target, sum, 0);
        return res;
    }
};

总结

当允许重复元素出现时，在进入下一层递归时就可以传入i而不是i+1。

因为给出的数组非递增，需要先对数组进行排序，优化效果不明显

组合总和II

[组合总和II](40. 组合总和 II - 力扣（LeetCode）)

回溯

该题与[II](# 组合总和II)的区别就在于输入的candidates数组允许有重复元素的出现，但每个元素只能使用一次，因此传递到下一层递归中的索引就必须是index+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
class Solution {
public:
    void traceback(vector<int>& candidates, vector<vector<int>>& res, vector<int>& vec, int target, int& sum, int startindex)
    {
        if (sum == target)
        {
            res.push_back(vec);
            return;
        }
        for (int i = startindex; i < candidates.size() && target > sum; i++)
        {
            vec.push_back(candidates[i]);
            sum += candidates[i];
            traceback(candidates, res, vec, target, sum, i);
            sum -= candidates[i];
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> vec;
        int sum = 0;
        traceback(candidates, res, vec, target, sum, 0);
        return res;
    }
};

此外，如果candidates中有重复元素，会导致同层的结点中可能会选取一样的值进入到下一层递归中，就会导致最终结果出现有相同元素的分组，如以上版本的代码，仅修改了上一题的index传递值。原因在于，可能会出现保存到res中的元素在回溯删除之后，因为相同值的元素存在，在遍历剩余元素时又被重新添加进去。

可以针对这种情况设立一个tmp变量，先对candidates进行排序，tmp记录刚被删除的元素的值，再下一个元素被添加时判断是否等于tmp，只有不相等时才会被添加进去。

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:
int tmp = 0;
    void traceback(vector<int>& candidates, vector<vector<int>>& res, vector<int>& vec, int target, int& sum, int startindex)
    {
        if (sum == target)
        {
            res.push_back(vec);
            return;
        }
        for (int i = startindex; i < candidates.size() && (target-sum) >= candidates[i]; i++)
        {
            if(tmp == candidates[i])
                continue;
            vec.push_back(candidates[i]);
            sum += candidates[i];
            traceback(candidates, res, vec, target, sum, i+1);
            sum -= candidates[i];
            tmp = candidates[i];
            vec.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> vec;
        int sum = 0;
        sort(candidates.begin(),candidates.end());
        traceback(candidates, res, vec, target, sum, 0);
        return res;
    }
};

另一种方法

1
2
3
4
5
6
7
8
9
10
for (int i = startindex; i < candidates.size() && (target-sum) >= candidates[i]; i++)
        {
            if(i > startindex && candidates[i] == candidates[i-1])
                continue;
            vec.push_back(candidates[i]);
            sum += candidates[i];
            traceback(candidates, res, vec, target, sum, i+1);
            sum -= candidates[i];
            vec.pop_back();
        }

回溯优化

剪枝优化过程同上题，以上版本代码已剪枝

总结

candidates没有重复元素，但结果输出可以有重复元素，则修改index

candidates有重复元素，但结果输出不能有重复元素，即相同元素的分组，则通过添加限制条件防止重复元素进入递归

分割回文串

[分割回文串](131. 分割回文串 - 力扣（LeetCode）)

回溯

相比较于之前的题目，该题变化点主要集中在于递归结束判断条件，在满足回文的条件的同时，还需要将整个字符串完全分割

  1. 确定递归结束条件

    1
    2
    3
    4
    5
    6
    if (index >= s.size())
    {
        if (judge())
           res.push_back(vec);
        return;
    }

    由于不能添加重复元素进入递归，所以需要index形参，需要在对整个字符串完成分割的时候才停止递归，并且要满足回文的条件才能保存结果

  2. 确定递归返回值

    1
    void traceback(string s, int index)

  3. 确定单层逻辑

    1
    2
    3
    4
    5
    6
    for (int i = index; i < s.size(); ++i)
    {
        vec.push_back(s.substr(index,i+1-index));
        traceback(s, i + 1);
        vec.pop_back();
    }

整体代码如下

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
class Solution {
public:
    vector<vector<string>> res;
    vector<string> vec;
    string str;

    bool judge()
    {
        for(auto sustr:vec)
        {
            int i = 0, j = sustr.size()-1;
            while(i<=j)
            {
                if(sustr[i]!=sustr[j])
                    return false;
                ++i,--j;
            }
        }
        return true;
    }
    void traceback(string s, int index)
    {
        if (index>=s.size())
        {
            if(judge())
                res.push_back(vec);
            return;
        }
        for (int i = index; i < s.size(); ++i)
        {
            vec.push_back(s.substr(index,i+1-index));
            traceback(s, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        if (s.size() == 1)
            return vector<vector<string>>{{s}};
        traceback(s, 0);

        return res;
    }
};

此外，还可以在进入递归前完成对回文串的判断

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 {
public:
    vector<vector<string>> res;
    vector<string> vec;

    bool judge(int st, int en,string s)
    {
        while(st<=en)
        {
            if(s[st]!=s[en])
                return false;
            ++st,--en;
        }
        return true;
    }
    void traceback(string s, int index)
    {
        if (index>=s.size())
        {
            res.push_back(vec);
            return;
        }
        for (int i = index; i < s.size(); ++i)
        {
            if(!judge(index,i,s))
                continue;
            vec.push_back(s.substr(index,i+1-index));
            traceback(s, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        if (s.size() == 1)
            return vector<vector<string>>{{s}};
        traceback(s, 0);

        return res;
    }
};

总结

难点在于

  • 切割问题转换成组合问题

    关键在于模拟出树形结构

  • 字符串分割如何用代码实现

    利用index，以及substr函数，把递归开始时的初值模拟为切割线

  • 判断回文串

    双指针法；动态规划

  • 递归结束条件的判断

复原IP地址

本题也属于切割问题，但切割完成的判断更为复杂，切割的IP地址分为4段，需要直接在原字符串中加上'.'表示分段，分段中的IP地址不能有前导0，不能大于255，否则都将是无效的IP。

转换成树形结构

首先，确定判断IP段是否有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool ok(const string& s, int st, int en)
{
	if(st > en)
		return false;
	if(s[st] == 0 && st!=en)
		return false;
	int num = 0;
	for(int i = st; i <= en; i++)
	{
		num = num*10 + (s[i] - '0');
		if(num > 255)
			return false;
	}
	return true;
}

如果仅仅是首元素为0还不一定无效，IP地址段可以只有一个0，但不能是前导0

计算IP地址段可以用for循环，逐位相加，一旦某一位已经超过255则直接返回false

回溯1

  1. 递归结束条件

    1
    2
    3
    4
    5
    6
    if(comma == 3)
    {
    	if(ok(s,index,s.size()-1))
    		res.push_back(s);
    	return;
    }

    因为是直接在源字符串中做分割，在加了3个'.'的情况下，还需要对最后一段IP进行判断是否有效才能加入到结果集中

  2. 递归返回值

    1
    void traceback(vector<string>& res, int comma, int index, string& s)

    因为直接在源字符串上操作，并且需要找到所有有效的IP地址，因此不需要返回值。传入参数为引用，不用拷贝并且允许直接修改、删除等操作

  3. 单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    for(int i = index; i < s.size(); i++)
    {
    	s.insert(s.begin() + i + 1, '.');
    	++comma;
    	traceback(res, comma, i + 2, s);
    	--comma;
    	s.erase(s.begin() + i + 1);
    }

    insert函数将'.'插在输入的迭代器之前，即取代输入的迭代器位置，erase则是删除输入迭代器当前位置上的元素。进入递归由于插入多了一位，则下一层递归中需要从index = i+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
class Solution {
public:
    bool ok(const string& s, int st, int en)
    {
        if (st > en)
            return false;
        if (s[st] == '0' && st != en)
            return false;
        int num = 0;
        for (int i = st; i <= en; i++) 
        {

            num = num * 10 + (s[i] - '0');

            if (num > 255) 
                return false;
        }
        return true;
    }
    void traceback(vector<string>& res, int index, int comma, string& s)
    {
        if (comma == 3)
        {
            if (ok(s, index, s.size() - 1))
            {
                res.push_back(s);
            }
            return;
        }
        for (int i = index; i < s.size(); i++)
        {
            if (ok(s, index, i))
            {
                s.insert(s.begin() + i + 1, '.');
                ++comma;
                traceback(res, i + 2, comma, s);
                --comma;
                s.erase(s.begin() + i + 1);
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        traceback(res, 0, 0, s);
        return res;
    }
};

回溯2

另外一种解法是， 不在源字符串上修改，而是将4段IP地址一段一段的加入一个空字符串中

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
class Solution {
public:
    vector<string>ans;
    void backtrace(string& s,int cnt,int index,string& str){
        if(cnt==4 || index==s.size() ){
            if(cnt==4 && index==s.size())
                ans.push_back(str.substr(0,str.size()-1));
            return;
        }
        for(int i=1;i<=3;i++){
            if(index+i>s.size()) return;
            if(s[index]=='0' && i!=1) return;
            if(i==3 && s.substr(index,i)>"255") return;
            str+=s.substr(index,i);
            str.push_back('.');
            backtrace(s,cnt+1,index+i,str);
            str = str.substr(0,str.size()-i-1);
        }
    }
    vector<string> restoreIpAddresses(string s) {
        string str ="";
        backtrace(s,0,0,str);
        return ans;

    }
};

总结

回溯1是从一整段IP地址直接做分割，回溯2则是将各段分割好的小段最终才拼凑成完整的IP地址，这样做的好处是对于各段统一判断是否有效，而不用像回溯1中在添加了最后一个'.'之后，添加到结果集之前还要做一次有效判断。并且在回溯2中，判断有效更加简洁，可以利用加入的子段最多只有3位直接与”255”进行判断，而回溯1中可能会出现不止3位的IP地址，因此不能直接与”255”判断，但可以修改成if(en - st == 2 && s.substr(s.begin() + st, 3) > "255") return false;以及if(en - st > 2) return false;

子集

回溯

子集问题中，依旧还是回溯的总体思路，不同在于之前结束条件的判断，仅仅只是遍历到数组结尾就退出

整体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void traceback(vector<int>&nums,vector<int>&vec,vector<vector<int>>&res,int index)
    {
        if(index>=nums.size())
            return;
        for(int i = index; i<nums.size();i++)
        {
            vec.push_back(nums[i]);
            res.push_back(vec);
            traceback(nums,vec,res,i+1);
            vec.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> vec;
        vector<vector<int>> res;
        res.push_back(vec);
        traceback(nums,vec,res,0);
        return res;
    }
};

总结

子集问题不需要有判断条件，就直接存入结果集中，相当于将树型结构上的每个结点；而组合和切割问题则是保留叶子结点

子集II

回溯

给定输入数组中含有重复元素，但要求输出结果中不能有重复子数组，与[组合总和II](# 组合总和II)思路一致，且其余同子集的处理

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:
    void traceback(vector<int>&nums,vector<int>&vec,vector<vector<int>>&res,int index)
    {
        if(index>=nums.size())
            return;
        for(int i = index; i<nums.size();i++)
        {
            if(i>index&&nums[i]==nums[i-1])
                continue;
            vec.push_back(nums[i]);
            res.push_back(vec);
            traceback(nums,vec,res,i+1);
            vec.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> vec;
        vector<vector<int>> res;
        res.push_back(vec);
        sort(nums.begin(),nums.end());
        traceback(nums,vec,res,0);
        return res;
    }
};

递增子序列

[递增子序列](491. 递增子序列 - 力扣（LeetCode）)

回溯

这道题需要理解的几个关键点：

  • 要求是子序列，则不能对其排序，有点类似于分割问题但可以只取两边不取中间，即[1,2,3]选[1,3]
  • 要求是非严格递增，则在进入递归前应先进行判断，
  • 输入数组中可能会有重复元素，但输出不能包含重复子数组

可知，需要在不能排序的情况下，还要在递归过程中排除重复项，回溯的时候应该借助容器来帮助辨别重复项，容易想到用unordered_set容器储存结果用于去除重复项，然后遍历容器将没有重复的元素依次存放到vector中，但是，不能直接定义unordered_set<vector<int>>，还要有自定义的哈希函数。因此可以转换思路，在每一层的结点循环中设置一个unordered_set，即单单不允许这一层有重复被选数，这就避免重复项进入递归，因为前一个所选就囊括了后面所有相同数的子序列。

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
class Solution {
public:
    void traceback(vector<int>& nums,vector<vector<int>> &res, vector<int>& vec,int index)
    {
        unordered_set<int> uset;
        if(index>=nums.size())
            return;
        for(int i = index;i<nums.size();i++)
        {
            if(i>index&&nums[i]==nums[i-1])
                continue;
            if(!vec.empty() && nums[i]<vec.back())
                continue;
            if(uset.find(nums[i])!=uset.end())
                continue;
            vec.push_back(nums[i]);
            uset.insert(nums[i]);
            if(vec.size()>1)
                res.push_back(vec);
            traceback(nums,res,vec,i+1);
            vec.pop_back();            
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> vec;
        traceback(nums,res,vec,0);
        return res;
    }
};

回溯优化1

以上版本的代码，用到了unordered_set，又因为总数据量较小，可以用vector替代unordered_set以减少开销

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
class Solution {
public:
    void traceback(vector<int>& nums,vector<vector<int>> &res, vector<int>& vec,int index)
    {
        vector<int> used(201,0);
        if(index>=nums.size())
            return;
        for(int i = index;i<nums.size();i++)
        {
            if(i>index&&nums[i]==nums[i-1])
                continue;
            if(!vec.empty() && nums[i]<vec.back())
                continue;
            if(used[nums[i]+100]==1)
                continue;
            vec.push_back(nums[i]);
            used[nums[i]+100] = 1;
            if(vec.size()>1)
                res.push_back(vec);
            traceback(nums,res,vec,i+1);
            vec.pop_back();            
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> vec;
        traceback(nums,res,vec,0);
        return res;
    }
};

回溯优化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
class Solution {
public:
    vector<int> vec;
    vector<vector<int>> res;
    void traceback(vector<int>&nums,int cur,int last)
    {
        if(cur>=nums.size())
        {
            if(vec.size()>1)
                res.push_back(vec);
            return;
        }
        if(nums[cur]>=last)
        {
            vec.push_back(nums[cur]);
            traceback(nums,cur+1,nums[cur]);
            vec.pop_back();
        }
        if(nums[cur]!=last)
            traceback(nums,cur+1,last);
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        traceback(nums,0,-101);
        return res;
    }
};

选择合法项：只有cur值大于等于last，才会选择该元素（添加到vec中）

不借助容器就能排除重复项：只有last和cur指向的值不相同时，才会不选择该结点（不添加到vec中），也就是说当有多个重复元素时，只选最后一个以避免重复

拓展

另一种回溯模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> ans;
vector<int> temp;
void dfs(int cur, vector<int>& nums) {
    if (cur == nums.size()) {
        // 判断是否合法，如果合法判断是否重复，将满足条件的加入答案
        if (isValid() && notVisited()) {
            ans.push_back(temp);
        }
        return;
    }
    // 如果选择当前元素
    temp.push_back(nums[cur]);
    dfs(cur + 1, nums);
    temp.pop_back();
    // 如果不选择当前元素
    dfs(cur + 1, nums);
}

[子集](# 子集)新解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> res;
vector<int> vec;
    void traceback(int cur, vector<int>&nums)
    {
        if(cur>=nums.size())
        {

            res.push_back(vec);
            return;
        }
        
        vec.push_back(nums[cur]);
        traceback(cur+1,nums);
        vec.pop_back();
        
        traceback(cur+1,nums);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        traceback(0,nums);
        return res;
    }
};

[子集II](# 子集II)新解法

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
class Solution {
public:
vector<vector<int>> res;
vector<int> vec;
    void traceback(int cur, vector<int>&nums)
    {
        if(cur>=nums.size())
        {
            res.push_back(vec);
            return;
        }

        vec.push_back(nums[cur]);
        traceback(cur+1,nums);
        vec.pop_back();

        while(cur < nums.size()-1 && nums[cur]==nums[cur+1])
            ++cur;
        traceback(cur+1,nums);
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        traceback(0,nums);
        return res;
    }
};

总结

该题最关键是在不排序的前提下，排除重复项进入递归，需要借助容器，并且是在每层递归中重新定义一个容器，从而避免同层相同元素进入递归

另一种回溯模板，不对应树形结构，因而更难理解；优先处理更多元素的情况，但因其一层两次递归，时间复杂度更高，但指针使用更加灵活，减少对容器的使用，降低空间复杂度

全排列

回溯

排列问题，容易得知，每次递归时需要从0开始遍历数组，这就意味着不能像组合总和一样代入index对递归进行限制。并且，需要借助容器来记录遍历的当前值是否有被使用过。将全排列转化成树形结构，则同一个树枝上不能够有重复值，那么就可以借助全局的vector进行记录，与vec同步增删元素。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void traceback(vector<int>& nums, int index,vector<int> &used)
    {
        if (vec.size() == nums.size())
        {
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (used[nums[i] + 10] == 1)
                continue;
            vec.push_back(nums[i]);
            used[nums[i] + 10] = 1;
            traceback(nums, index + 1,used);
            used[nums[i] + 10] = 0;
            vec.pop_back();

        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(21, 0);
        traceback(nums, 0,used);
        return res;
    }
};

与[递增子序列](# 递增子序列)一样，可以通过unordered_set以及vector来记录，vector在数组样本小的情况下性能更加优越

总结

  • 组合之和：只能往后选取（排列顺序不影响结果），故需要用index记录每次递归开始选取的位置；去重则通过排序后再对当前值进行是否与前值重复判断
  • 分割：与组合之和差别在于终止条件，分割必须要字符串全部分割
  • 子集：与组合之和差别在于子集的每个结点都是结果集
  • 全排列：不需要index记录每次递归开始选取的位置，因为有排列顺序要求；去重因为没有index，需要借助容器来记录是否被选取过，通常选vector

全排列II

回溯1

在[全排列](# 全排列)基础上，输入数组可能会有重复值，即不仅在树枝上不能够有重复值，在树层上也不允许有重复值的存在，但是不能直接加上排序后再判断当前值与前一值是否相等的去重操作。因为重复值的存在，当在同一条路径上，即树枝上允许有重复值的存在（来源于不同的等值元素），针对树枝上的重复值，可以借助vector先遍历nums记录每个数值的个数，用来判断这个树枝上是否还能使用该数值

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 {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void traceback(vector<int>& nums, int index,vector<int> &used)
    {
        if (vec.size() == nums.size())
        {
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (used[nums[i] + 10] == 0)//树枝去重
                continue;
            if(i>0&&nums[i]==nums[i-1])//树层去重，同时防止树枝上取已取过的值
                continue;
            vec.push_back(nums[i]);
            --used[nums[i] + 10];
            traceback(nums, index + 1,used);
            ++used[nums[i] + 10];
            vec.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(21, 0);
        sort(nums.begin(),nums.end());
        for(int i:nums)
        {
            ++used[i+10];
        }
        traceback(nums, 0,used);
        return res;
    }
};

关键语句在于if(i>0 && nums[i]==nums[i-1]) continue;，既做到了对同一层上的结点去重，也做到在一棵树枝上对取过的值的去重（全排列的要求，相当于全排列中的used数组）

回溯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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void traceback(vector<int>& nums,vector<bool> &used)
    {
        if (vec.size() == nums.size())
        {
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)//树层去重
                continue;
            if(used[i]==false)//树枝去重
            {
                used[i]=true;
                vec.push_back(nums[i]);
                traceback(nums,used);
                used[i]=false;
                vec.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(),nums.end());
        traceback(nums,used);
        return res;
    }
};

直观的用used数组表示原始数组中的每一个值是否使用过，是对全排列的进一步改进。不只是加上直接加上排序后再判断当前值与前一值是否相等的去重操作，为了防止树枝上的多余去重，额外增加了&&used[i-1]==false，限定了只在树层上去重，而不影响树枝上对等值元素的取用

总结

在全排列的基础上，只增加if(i>0 && nums[i]==nums[i-1]) continue;语句会导致竖向上首元素会被重复加入（因为i从0开始），而语句本意是跳过横向重复结点和跳过已加入的竖向重复结点，因此，要么选择再增加对跳过竖向结点的限制，如[回溯2](# 回溯2)用额外used数组记录每个元素是否被访问过，如果前一个元素未被访问nums[i-1]==false，且满足当前元素与前一个元素相同i>0 && nums[i]==nums[i-1]，证明这是在横向上的重复结点（树层），应当跳过，而竖向上如果再次访问访问过的结点used[i]==true，则会执行跳过，不重复加入结果中（另一个角度，如果在满足当前元素与前一个元素相同i>0 && nums[i]==nums[i-1]时，前一个元素被访问过nums[i-1]==true，此时当前元素也可以被跳过，保留的是横向上的结点，而竖向重复结点被跳过）；要么在if(i>0 && nums[i]==nums[i-1]) continue;语句不能跳过已加入的竖向重复结点和横向重复结点的情况下，限制加入的重复结点数量如[回溯1](# 回溯1)用used数组记录每一个结点的数量，那么当i从开始时，只会最多加入原数组数量的元素，一旦超过就会被跳过。以上两种算法过程都如下图，

重新安排行程

回溯

本题中，关键点在于

  • 记录出发机场和目标机场的容器，同时还要记录是否访问过，防止死循环
  • 回溯的终止条件，因为一定存在合理路径，所以机票数+1 = 机场数
  • 容器按字典序排列目标机场，若访问字典序较高的目标机场时，该机场是死胡同，则应返回或者回溯
  • 回溯的返回值应该是bool类型，用返回值来判断是否应该回溯（删除死胡同元素）

  1. 递归终止条件

    1
    2
    3
    4
    if(tickets.size()==res.size()-1)
    {
    	return true;
    }

  2. 递归返回值

    1
    bool traceback(vector<string>&res,vector<vector<string>>& tickets)

    当返回值为true时，意味着已添加到结果集的元素符合要求，应该直接返回，而不应回溯（删除）；但当返回值为false时，代表着根据字典序优先访问到的这个机场无法再访问其他机场，是个死胡同，应该回溯（pop_back)

  3. 递归单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    for(auto const & ticket:tickets[res[res.size()-1]])
    {
    	if(ticket.second>0)
    	{
    		res.push_back(ticket.first);
    		ticket.second--;
    		if(traceback(res,tickets))	return true;
    		ticket.second++;
    		res.pop_back();
    	}
    }
    return false;

    上述代码在取目的机场的map时，使用范围for循环，auto &ticket:tickets[res[res.size()-1]]等价于pair<const string,int> &ticket:tickets[res[res.size()-1]]，其中因为map的key值不能改变，所以一定要用const引用，或者只是用副本pair<string,int>ticket:tickets[res[res.size()-1]]。而当不使用范围for循环时，类型符就要更改为map<const string, int>& ticket = tickets[res[res.size()-1]]，因为赋值需要同样的类型或者可转变的类型，而pair不能转变为map

整体代码如下

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 {
public:
    unordered_map<string, map<string, int>> targets;
    bool traceback(vector<string>& res, vector<vector<string>>& tickets)
    {
        if (res.size() == tickets.size() + 1)
        {
            return true;
        }
        for(auto& target:targets[res[res.size()-1]])
        {
            if(target.second>0)
            {
                target.second--;
                res.push_back(target.first);
                if(traceback(res,tickets))return true;
                res.pop_back();
                target.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> res;
        res.push_back("JFK");
        for (auto ticket : tickets)
        {
            targets[ticket[0]][ticket[1]]++;
        }
        traceback(res, tickets);
        return res;
    }
};

special解法

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:
    unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;

    vector<string> stk;

    void dfs(const string& curr) {
        while (vec.count(curr) && vec[curr].size() > 0) {
            string tmp = vec[curr].top();
            vec[curr].pop();
            dfs(move(tmp));
        }
        stk.emplace_back(curr);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& it : tickets) {
            vec[it[0]].emplace(it[1]);
        }
        dfs("JFK");

        reverse(stk.begin(), stk.end());
        return stk;
    }
};

按字典序从priority_queue中访问目标机场，对新访问的机场进行深度有限搜索，并删除访问过的机场，直到该机场是最后一个机场，则添加到数组当中，再不断返回，将之前访问过的机场也添加到数组中，最后将数组逆序即为结果集

总结

该题巧妙选择容器，记录复杂的信息，用unordered_map记录出发机场和目标机场，是因为不需要对出发机场进行排序，为了减少开销，用map<string,int>按字典序记录目标机场及机票数，不使用multiset单纯记录目标机场，就是为了防止同一张机票的重复访问，防止死循环

在第二种解法中，使用不用的容器来记录，通过优先队列来按字典序记录目标机场，每次访问只需要p.top()，访问时间复杂度是O(1)，删除的时间复杂度是O(logm)

破解保险箱

N皇后

[N皇后](51. N 皇后 - 力扣（LeetCode）)

要求在n*n的棋盘上放置n个皇后，并且皇后互相不能攻击，即同行同列包括斜角线上不能有两个皇后

逐行遍历棋盘，因为只需要在一行中摆放一个皇后，则不需要两层循环遍历，同时还要有判断是否冲突的函数

首先，根据规则判断在该位置上放置皇后是否会被攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool noattack(vector<string>& chessboard, int n, int index, int row)
{
	//列
	for(int i = 0;i < n;i++)
	{
		if(chessboard[i][index] == 'Q')
			return false;
	}
	
	//左上角斜线
	for(int i = row - 1, j = index - 1; i >= 0 && j >= 0; i--, j--)
	{
		if(chessboard[i][j] == 'Q')
			return false;
	}
	
	//右上角斜线
	for(int i = row - 1, j = index + 1; i >= 0 && j < n; i--, j++)
	{
		if(chessboard[i][j] == 'Q')
			return false;
	}
	return true;
}

因为是每一行遍历，因此不需要判断同行是否还有其他皇后；也因为是逐行往下遍历，不需要判断下方是否还有其他皇后，仅判断左上和右上方即可

回溯

  1. 确定递归结束条件

    1
    2
    3
    4
    5
    if(chessboard.size()==n)
    {
    	res.push_back(chessboard);
    	return;
    }

    不断添加单行到棋盘中，当棋盘中数量达到n时，就是一个符合要求的棋盘摆法

  2. 确定递归返回值

    1
    2
    void traceback(...)

    因为可能有多种不同符合规则的摆法，因此返回值为void，遍历所有可能值再返回

  3. 确定单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (int i = 0; i < n; i++)
    {
        if (noattack(chessboard, n,index,i))
        {
            chessboard[index][i] = 'Q';
            traceback(res, n, chessboard, index + 1);
            chessboard[index][i] = '.';
        }
    }

    对单行棋盘中皇后的摆放位置进行枚举，再递归进入下一行，如果发生相互攻击（遍历完所有值都不符合要求）则进行回溯，不发生攻击则继续递归下一行，直到满足要求

整体代码如下

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
class Solution {
public:
    bool noattack(const vector<string>& chessboard, int n, int row, int column)
    {
        for (int i = 0; i <= row; i++)
        {
            if (chessboard[i][column] == 'Q')
                return false;
        }

        for (int i = row - 1, j = column - 1; i >= 0 &&j >= 0; --i, --j)
        {
            if (chessboard[i][j] == 'Q')
                return false;
        }

        for (int i = row - 1, j = column + 1; i >= 0 && j < n; --i, ++j)
        {
            if (chessboard[i][j] == 'Q')
                return false;
        }
        return true;
    }
    void traceback(vector<vector<string>>& res, int n, vector<string>& chessboard, int index)
    {
        if (index >= n)
        {
            res.push_back(chessboard);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (noattack(chessboard, n,index,i))
            {
                chessboard[index][i] = 'Q';
                traceback(res, n, chessboard, index + 1);
                chessboard[index][i] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        vector<vector<string>> res;
        traceback(res, n, chessboard, 0);
        return res;
    }
};

总结

该题的关键点在于

  • 不需要两层循环，虽然是二维棋盘，但N皇后中不需要在二维棋盘的每一个点上都要放置皇后，仅是判断当前的点是否能放，因此使用单层循环
  • 回溯不需要返回值，是因为要寻找所有可行的棋盘摆放，应当用全局变量或者引用返回，同时要遍历所有情况；若只需要找到一种可行的棋盘，则返回值应为**bool，一旦找到则返回true退出递归**
  • 不需要对同行皇后进行判断，是因为对同行位置进行遍历时，肯定不会发生同一行同时有两个皇后出现，一旦某一个位置能够摆放皇后，就会马上进入到下一层递归，即到下一行的遍历，而后面回溯回本行时，又会将原位置的皇后删除，再从下一位进行遍历

解数独

[解数独](37. 解数独 - 力扣（LeetCode）)

与上题N皇后相比，解数独也是在一个二维棋盘上，但不仅要判断该点是否会有冲突，还要在遍历时在每个点上都要填充数字，也就是说，不能像上题一样，如果是单层循环，填完该位置上的数字就进入递归，遍历下一行。因此需要两层循环，填完数字后进入递归，还是从刚填过的位置开始继续填。

同样，首先需要根据规则判断是否有冲突

  • 同行不能有重复数字
  • 同列不能有重复数字
  • 同一个3x3格子不能有重复数字
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
bool ok(vector<vector<char>> & chessboard,int row, int col, int tmp)
{
	//判断列
	for(int i = row;i<9;i++)
	{
		if(chessboard[i][col]==tmp+'0')
			return false;
	}
	
	//判断行
	for(int j = 0;j<9;j++)
	{
		if(chessboard[row][j]==tmp+'0')
			return false;
	}
	
	//判断9宫格
	int subrow = (row / 3) * 3;	//0,1,2行等于0, 3,4,5行等于3，6,7,8行等于6
	int subcol = (col / 3) * 3;	
	for(int i = subrow; i < subrow + 3; i++)
	{
		for(int j = subcol; j < subcol + 3; j++)
		{
			if(board[i][j]==tmp+'0')
				return false;
		}
	}
	return true;
}

可知，需要多次的循环来完成一次的判断。则可以用哈希表的方法，先储存已有的数字，然后在一次循环完成冲突的判断

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
//全局变量
int row[9][10] {0};
int col[9][10] {0};
int subbox[9][10] {0};

//先完成对棋盘上已有数字的存储
for(int i = 0; i < 9; i++)
{
	for(int j = 0; j < 9; j++)
	{
		if(chessboard[i][j]!='.')
		{
			int tmp = chessboard[i][j]-'0';
			row[i][tmp] = 1;
			col[j][tmp] = 1;
			subbox[j/3 + (i/3)*3][tmp] = 1;
		}
	}
}

bool ok(int i, int j, int tmp)
{
	if(row[i][tmp]==1)
		return false;
	if(col[j][tmp]==1)
		return false;
	if(subbox[j/3+(i/3)*3][tmp]==1)
		return false;
	row[i][tmp] = 1;
	col[j][tmp] = 1;
	subbox[j/3+(i/3)*3][tmp] = 1;
	return true;
}

将三种规则分别替换为三个用二维数组记录的哈希表，行表（row）用第一维表示对应的行数，用第二维表示该行上出现过的数字0-9，如果出现过则置为1，列表（col）同理；由于9宫格中刚好有九个数字，也可以用同样的方法来记录，将棋盘上行列号映射为9个不同的9宫格序号，再记录出现过的数字

回溯

  1. 确定递归结束条件

    因为结束时，总是需要遍历棋盘上所有位置，当遍历结束也就是递归的结束，因此不需要递归的结束条件

  2. 确定递归返回值

    1
    bool traceback(vector<vector<char>>& chessboard, int row, int col)

    因为只需要寻找到一种符合的答案，一旦遇到有，则应立即退出递归并返回

  3. 递归单层逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    for(int i = 0;i<9;i++)
    {
    	for(int j = 0;j<9;j++)
    	{
    		if(chessboard[i][j]=='.')
    		{
    			for(int tmp = 1;tmp<10;tmp++)
    			{
    				if(ok(i,j,tmp))
    				{
    					chessboard[i][j]=tmp+'0';
    					if(traceback(chessboard)) return true;
    					chessboard[i][j]='.';
    					row[i][tmp] = 0;
    					col[j][tmp] = 0;
    					subbox[j/3+(i/3)*3][tmp] = 0;
    				}
    			}
    			return false;
    		}
    	}
    }
    return true;

整体代码如下

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:
int row[9][10] = {0},column[9][10] = {0}, subbox[9][10] = {0};
    bool ok(int i, int j, int tmp)
    {
        if(row[i][tmp]==1)
            return false;
        if(column[j][tmp]==1)
            return false;
        if(subbox[j/3+(i/3)*3][tmp]==1)
            return false;
        row[i][tmp] = 1;
        column[j][tmp] = 1;
        subbox[j/3+(i/3)*3][tmp] = 1;
        return true;
    }
    bool traceback(vector<vector<char>>& board)
    {
        for(int i = 0;i<9;i++)
        {
            for(int j = 0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    for(int tmp = 1;tmp<10;tmp++)
                    {
                        if(ok(i,j,tmp))
                        {
                            board[i][j] = tmp+'0';
                            if(traceback(board)) return true;
                            board[i][j] = '.';
                            row[i][tmp] = 0;
                            column[j][tmp] = 0;
                            subbox[j/3+(i/3)*3][tmp] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0;i<9;i++)
        {
            for(int j = 0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    int tmp = board[i][j]-'0';
                    row[i][tmp] = 1;
                    column[j][tmp] = 1;
                    subbox[j/3+(i/3)*3][tmp] = 1;
                }
            }
        }
        traceback(board);
    }
};

总结

该题的关键点在于

  • 递归中需要用双层循环，如果单层循环，则在该行填入一个数字之后进入递归，不管传入怎样的参数都不能使继续填充该行并且完成换行继续填充
  • 递归不需要结束条件，因为题目需要对棋盘上所有点都进行一次遍历，递归结束时就是得到结果时，即遍历结束即为递归结束
  • 递归需要返回值，题目保证能找到一个有效的解决方案，且最多只有一个解，因此返回bool值，当找到时，即遍历完棋盘，就返回true；当在棋盘上某一个点遍历完9个数字都没有合适结果时，应当返回false，令上一层递归进行回溯。也就是说，有返回值如bool类型，可以通过判断返回值（如果为真）可以避免进一步递归，同时还能让进入多余分支的递归及时退出，防止了死循环（如本题，在没有递归结束条件的情况下，如果不用返回值限制则会导致死循环）；而无返回值的通常是要遍历所有分支，从中找到所有解
  • 一次循环即可完成对数独是否有效的判断，借助哈希表，将一维的数据通过二维的哈希表进行重复性判断

最接近目标价格的甜点成本

该题要求从必选数组base中选择一份基料，以及从可选数组topping中选择0份、1份或者2份配料，组成的冰淇淋总价格最接近target且成本最低

回溯

容易想到，给定数据量较少，可以用回溯算法对数组进行遍历，用set保存可行的方案，并最终选择最合适的一个价格返回

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
class Solution {
public:
    set<int> vec;
    void traceback(vector<int>& toppingCosts, int target, int index, int res)
    {
        if (index == toppingCosts.size())
        {
            return;
        }
        for (int i = index; i < toppingCosts.size(); i++)
        {
            res += toppingCosts[i];
            vec.insert(res);
            traceback(toppingCosts, target, i + 1, res);
            res += toppingCosts[i];
            vec.insert(res);
            traceback(toppingCosts, target, i + 1, res);
            res -= toppingCosts[i] * 2;
        }
    }
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int res = 0;
        //int m = toppingCosts.size();
        //for (int i = 0; i < m; i++)
        //{
        //    toppingCosts.push_back(toppingCosts[i]);
        //}
        for (int i = 0; i < baseCosts.size(); i++)
        {
            res = baseCosts[i];
            vec.insert(res);
            traceback(toppingCosts, target, 0, res);
        }
        int ans = INT_MAX;
        for (auto it: vec)
        {
            if (abs(target - it) < abs(ans - target))
                ans = it;
            else if(abs(target - it == abs(ans-target)))
                ans = it < ans? it:ans;
        }
        return ans;
    }
};

因为最多可以添加两份配料，则将原数组topping中的元素都复制一遍，再进行回溯，但会超时

则可以对数组topping中的同一个元素进行两次回溯递归，分别将一份和两份配料的价格传递到递归当中

无论价格是多少，都会被存入到set当中，因为难以在存入结果之前对结果的合法性进行判断，所以只能被动地存入所有结果，最后在遍历所有结果的时候，选取最合适的结果

回溯优化

优化在只需要用O(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:
    int ans = INT_MAX;
    void traceback(vector<int>& toppingCosts, int target, int index, int res)
    {
        if (abs(target-ans) > abs(res-target))
            ans = res;
        if(abs(target-ans) == abs(res-target) && res < ans )
            ans = res;
        if(res > target)
            return;
        for (int i = index; i < toppingCosts.size(); i++)
        {
            traceback(toppingCosts, target, i + 1, res + toppingCosts[i]);
            traceback(toppingCosts, target, i + 1, res+ 2 * toppingCosts[i]);
        }
    }
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int res = 0;
        for (int i = 0; i < baseCosts.size(); i++)
        {
            res = baseCosts[i];
            traceback(toppingCosts, target, 0, res);
        }
        return ans;
    }
};

总结

回溯算法的题目要注意回溯参数i与 index，如果是i，则是允许元素重复加入结果集，在本题中，使用i作为参数传递而不是i+1，则意味着可以使用任意数量的配料topping，不符合题意；添加元素到结果集时，向递归函数传递的参数永远都是i而不是index

因为有必选数组和可选数组的存在，对必选数组进行for循环遍历，再进行回溯，保证结果集中有必选数组的元素；而必选数组中又可以对不同数量的元素重复使用（同一个元素最多两次），则可以通过两次回溯调用来实现

LeetCode回溯算法章节
https://kevin346-sc.github.io/2022/11/05/LeetCode回溯算法章节/
作者
Kevin Huang
发布于
2022年11月5日
许可协议