leetcode 之回溯问题

发表于 | 更新于 | 评论数： | 阅读次数：

回溯算法

定义

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

主要策略

保存当前步骤，如果是一个解就输出；维护状态，使搜索路径（含子路径）尽量不重复。必要时，应该对不可能为解的部分进行剪枝(pruning)。

leetcode例题

22. Generate Parentheses

  • 给出n个括号的排列组合，Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()”]
  • 思路：每个位置都进可以放 ( 或 ) ，但当此位置前没有单独的 ( 时，不能放置 )，建立一个变量记录没有配对的 ( 个数，然后递归求解。
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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string p="";
        if(n==0)return res;
        getStr(res,p,n,0);
        return res;
    }
    void getStr(vector<string> &res,string &p,int n,int right)
    {
        if(n==0)
        {
            string s=p,s1(right,')');
            s+=s1;
            res.push_back(s);
        }
        else if(right==0) //right==0，此时只能添加(
        {
            p.push_back('(');
            getStr(res,p,n-1,right+1);
            p.pop_back();
        }
        else
        {
            p.push_back('(');
            getStr(res,p,n-1,right+1);
            p.pop_back();
            p.push_back(')');
            getStr(res,p,n,right-1);
            p.pop_back();
        }
    }
};

39. Combination Sum

  • Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.The same repeated number may be chosen from candidates unlimited number of times.
  • 此类问题的关键是若满足条件，则将解保存，否则需正确回溯到上一步空间状态，我的思路是：对于第i个元素，有放与不放2种状态，则用递归方式依次搜索着2种状态，另外将数组预先排序，可以降低搜索时间。需要吐槽的是，自己的代码功力还是太弱鸡，开始以为递归的话，sums数组在函数中会被修改，好像就递归不起来了，于是传了个虚参，后来发现可以用实参。然后刚开始考虑，对于第i个元素，我居然写出3种状态来了，然后result最后也传了个虚参，submit后，输出空结果，检查了半天，发现result前面少写了个&。最后总共花了一个多小时，效率太慢了。
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>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> sums;
        if(candidates.size()==0) return result;
        int begin=0;
        sort(candidates.begin(), candidates.end());
        getSum(candidates,target,begin,sums,result);
        return result;
    }
    void getSum(vector<int>& candidates, int target,int begin,vector<int> &sums,vector<vector<int>>& result)
    {
        if(candidates[begin]<target)
        {
            sums.push_back(candidates[begin]);
            getSum(candidates,target-candidates[begin],begin,sums,result);//将第i个元素放入解数组并搜索
            sums.pop_back();
            if(begin+1<candidates.size())
            {
                getSum(candidates,target,begin+1,sums,result);//第i个元素不放，并开始考虑i+1元素
            }
        }
        else if(candidates[begin]==target)
        {
            sums.push_back(candidates[begin]);
            result.push_back(sums);
            sums.pop_back();
        }
        else
        {
            return;
        }
    }
};

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 sums to target.Each number in candidates may only be used once in the combination.
  • 大体思路与上题一样，感觉没什么区别，就是一个元素只能用1次了，然后我啪啪啪一会就写完，一运行发现结果错了，仔细检查发现，重复的元素会造成干扰，如[1,1,2,3,4]，target=3，我的结果是[[1,2],[1,2]]，这两个1分别是第一、第二个1，然后想到，要么输出结果后对res数组去重，但这样复杂度太高了，于是第二步想用哈希表，将结果插入res数组时先在哈希表中搜索一下，但我哈希表用的不熟悉，写了一会，用的unordered_map<vector,int>，结果还是报错了，不知道是不是vector不能做键值，于是用了第三种方法，思路是：对于第i个元素，有放与不放2种状态，但对于重复元素而言（比较candidates[i]==candidates[i+1]），仅对如果放，按以前一样递归搜索，不放则递归搜索下一个不重复元素。还是以[1,1,2,3,4]为例，如果第一个1放，则考虑第二个1放不放，如果第一个1不放，则考虑第三个元素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
    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> res;
            vector<int> vec1;
            if(candidates.size()==0) return res;
            sort(candidates.begin(),candidates.end());
            getSum(candidates, target,res,vec1,0);
            return res;
        }
        void getSum(vector<int>& candidates, int target,vector<vector<int>> &res,vector<int> &vec1,int begin)
        {
            if(candidates[begin]<target&&begin<candidates.size()-1)
            {
                vec1.push_back(candidates[begin]);
                getSum(candidates, target-candidates[begin],res,vec1,begin+1);
                vec1.pop_back();
                int i=1;
                while(begin+i<candidates.size()-1)
                {
                    if(candidates[begin]<candidates[begin+i])
                        break;
                    i++;
                }
                getSum(candidates, target,res,vec1,begin+i);
            }
            else if(candidates[begin]==target)
            {
                vec1.push_back(candidates[begin]);
                res.push_back(vec1);
                vec1.pop_back();
            }
        }
    };

46. Permutations

  • Given a collection of distinct integers, return all possible permutations.
  • 递归问题
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> > permute(vector<int> &num) {
	    vector<vector<int> > result;
	    
	    permuteRecursive(num, 0, result);
	    return result;
    }
    
    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
	void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
		if (begin >= num.size()) {
		    // one permutation instance
		    result.push_back(num);
		    return;
		}
		
		for (int i = begin; i < num.size(); i++) {
		    swap(num[begin], num[i]);
		    permuteRecursive(num, begin + 1, result);
		    // reset
		    swap(num[begin], num[i]);
		}
    }
};

51. N-Queens

  • N皇后问题，皇后可以直走与走对角线。
  • 这里用python写的代码，还遇到一些坑，因为python的类用的不熟练，调用类内调用成员函数要用self.fun()，感觉自己写的很啰嗦，写了40+行，评论区大神明明10+行就能写完，而且写完还花很多时间调bug。
  • 另外N皇后问题又如下特殊性质：如果1皇后坐标为(x,y)，则其他皇后不能出现在(p,q)，p与q满足：p+q!=x+y and p-q != x-y，这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
class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        q=[]
        nq=[]
        if(n==1):
            return [['Q']]
        self.solves(q,nq,n,0,0)
        res=[]
        for i in range(len(nq)):
            res.append([])
            for j in range(n):
                line=''
                for k in range(n):
                    if(k!=nq[i][j]):
                        line+='.'
                    else:
                        line+='Q'
                res[-1].append(line)
        return res
    def solves(self,q,nq,n,i,j):
        if(len(q)==0):
            for l in range(n):
                q.append(l)
                self.solves(q,nq,n,i+1,0)
                q.pop()
        else:
            for k in range(i):
                if((q[k]==j or q[k]+i-k==j or q[k]-i+k==j)):
                    if(j<n-1):
                        self.solves(q,nq,n,i,j+1)
                    break
                elif(k==i-1):
                    if(i!=n-1):
                        if(j<n-1):
                            self.solves(q,nq,n,i,j+1)
                        q.append(j)
                        self.solves(q,nq,n,i+1,0)
                        q.pop()
                    else:
                        q.append(j)
                        nq.append([])
                        nq[-1]+=q
                        q.pop()

评论区解法：

1
2
3
4
5
6
7
8
9
10
11
12
def solveNQueens(self, n): 
    def DFS(queens, xy_dif, xy_sum):# p 与 q 分别代表横纵坐标
        p = len(queens)
        if p==n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
    result = []
    DFS([],[],[])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

52. N-Queens II

  • 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
25
26
27
28
29
30
31
32
33
34
class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.z=0
        q=[]
        nq=[]
        if(n==1):
            return 1
        self.solves(q,nq,n,0,0)
        return self.z
    def solves(self,q,nq,n,i,j):
        if(len(q)==0):
            for l in range(n):
                q.append(l)
                self.solves(q,nq,n,i+1,0)
                q.pop()
        else:
            for k in range(i):
                if((q[k]==j or q[k]+i-k==j or q[k]-i+k==j)):
                    if(j<n-1):
                        self.solves(q,nq,n,i,j+1)
                    break
                elif(k==i-1):
                    if(i!=n-1):
                        if(j<n-1):
                            self.solves(q,nq,n,i,j+1)
                        q.append(j)
                        self.solves(q,nq,n,i+1,0)
                        q.pop()
                    else:
                        self.z+=1

78. Subsets

  • Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.
  • 递归问题
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:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> r1;
        if(nums.size()==0) return res;
        subs(nums,res,r1,0);
        return res;
    }
    void subs(vector<int>& nums,vector<vector<int>>& res,vector<int>& r1,int pos)
    {
        if(pos<nums.size()-1)
        {
            r1.push_back(nums[pos]);
            subs(nums,res,r1,pos+1);
            r1.pop_back();
            subs(nums,res,r1,pos+1);            
        }
        else
        {
            res.push_back(r1);
            r1.push_back(nums[pos]);
            res.push_back(r1);
            r1.pop_back();
        }
    }
};

90. Subsets II

  • Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power 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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        set<vector<int> > res;
        vector<vector<int> > res1;
        vector<int> x;
        if(nums.size()==0){
            vector<int> emptys;
            res1.push_back(emptys);
            return res1;
        }
        sort(nums.begin(),nums.end());
        subset(nums,x,res,0);
        for(auto i=res.begin();i!=res.end();i++){
            res1.push_back(*i);
        }
        return res1;
    }
    void subset(vector<int>& nums,vector<int>& x,set<vector<int> > &res,int pos){
        if(pos>=nums.size()){
            res.insert(x);
            return;
        }
        x.push_back(nums[pos]);
        subset(nums,x,res,pos+1);
        x.pop_back();
        subset(nums,x,res,pos+1);
    }
};

本文标题:leetcode 之回溯问题

文章作者:微石

发布时间:2018年05月23日 - 21:05

最后更新:2018年07月19日 - 11:07

原始链接:akihoo.github.io/posts/8d04a03b.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。