Leetcode学习：五大算法之回溯算法

1 简介

1.1 介绍

百度百科给出的定义如下：
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

显而易见，这个算法和深度优先遍历有着紧密的联系，都是“一走走到头，走到头就回身到下一个岔路口继续走到头”的类型。但不同于DFS的是需要有一个“状态重置”的操作，因为每一次“走到头”都对应到了一个解，返回时若没有状态重置就相当于又一次重复，且丢失了解空间的其他解。

1.2 算法核心

回溯 = DFS + 状态重置 （+ 剪枝）

2 解答模板

void backTrack(track ,allChoise)
{
	if('结束条件')//到达了最底层
	{
		'结束操作';
		return;
	}
	for(i : allChoise)
	{
		allChoise[i] = true;
		backTrack(track+1, allChoise)//回溯：本质是DFS
		allChoise[i] = false;//状态重置
	}
}

3 例题

根据解答模板，我们可以将以下回溯法的经典例题套进去，来看一下回溯的威力。

3.1 全排列问题

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int begin = 0;
        int end = nums.size();

        vector<int> result;
        vector<vector<int>> ret;

        dfs(nums,result,ret,begin,end);
        return ret;
    }

    void dfs(vector<int>& nums, vector<int> result, vector<vector<int>>& ret, int begin, int end)
    {
        if(begin == end - 1)
        {
            ret.push_back(nums);
            return;   
        }

        for(int  i = begin; i < end; i++)
        {
            swap(nums[begin],nums[i]);
            result.push_back(nums[i]);
            
            dfs(nums,result,ret,begin+1,end);

            swap(nums[begin],nums[i]);
            result.pop_back();
                
        }

    }

    void swap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};

3.2 N皇后问题

#include<iostream>
#include<vector>

using namespace std;

vector<vector<string>> ans;//存储N皇后的解

bool isok(vector<int>& record, int row)//record[row]就是col
{
	for (int i = 0; i < row; i++)
	{
		if (record[i] == record[row]
			|| row - record[row] == i - record[i]
			|| row + record[row] == i + record[i])
		{
			return false;
		}		
	}
	return true;
}

void findQueue(int row, int n, vector<string>&temp, vector<int>& record)
{
	if (row == n)//N皇后有解了
	{
		ans.push_back(temp);//把解放进全部解空间中
		return;
	}
	for (int col = 0; col < n; col++)
	{
		record[row] = col;

		if (isok(record, row))//回溯的过程：record表示在第几列（这一行的第几个位置），l表示在第几行
		{
			temp[row][col] = 'Q';//设为Q递归回溯一下
			findQueue(row + 1, n, temp, record);//去下一行找
			temp[row][col] = '.';//不论找没找到，回归原始状态继续找
		}
	}
}

vector<vector<string>> solveNQueens(int n)
{
	string s = "";
	vector<int> record(n);//初始化为n个0
	for (int i = 0; i < n; i++)
	{
		s += '.';
	}
	vector<string> temp(n, s);//初始化为全是.的nxn的二维数组


	findQueue(0, n, temp, record);//findQueue
	return ans;
}



int main()
{
	vector<vector<string>> ret = solveNQueens(4);

	system("pause");
	return 0;
}

3.3 解数独问题

bool isValidPart(char **board, int i, int j, int *a)
{
    char c = board[i][j];
    if(c != '.')
    {
        int index = c - '1';
        if(a[index]==1)return false;
        else a[index]=1;
    }
    return true;
}

bool isValidSudoku(char** board, int boardRowSize, int boardColSize)
{
    if(boardRowSize != 9|| boardColSize != 9)
    	return false;
    int a[9]={0};  //标记一行
    int b[9]={0};  //标记一列
    int c[9][9]={0}; //c[i]标记一个9宫格
    
    for(int i = 0; i < 9; i++)
    {
        memset(a,0,sizeof(int)*9);
        memset(b,0,sizeof(int)*9);
        
        for(int j = 0; j < 9; j++)
        {
            if(isValidPart(board, i, j, a)==false)
            	return false;
            if(isValidPart(board, j, i, b)==false)
            	return false;
            if(isValidPart(board, i, j, c[(i/3)*3 + j/3])==false)
            	return false;
        }
    }
    return true;
}