回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，
尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目
标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称.

通常回溯算法需要搭配上剪支,否则时间复杂度会很高(因为是遍历每一种题目所要求的可能结果)

BFS

广度优先算法实际在二叉树中就是层序遍历,通常是利用一个队列来存储每一层的节点进行遍历,在图中的话需要增加一个存储访问标识的数组.

DFS

深度优先算法在二叉树中对应的是前、中、后序遍历,通常是用递归的方法来遍历.在图中的话需要在递归函数的参数中传递一个存储访问标识的数组.

LeetCode - 46 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

这就是一个很典型的回溯题目，需要将所有可能的结果都枚举出来并返回.我们可以用DFS 或者 BFS 都可以。实际上感觉在回溯的题目中这两种办法都能解决问题只是复杂程度不一样。

图片来源 liweiwei1419

代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > ret;
        vector<int> tmp;  //用于临时存放每一种排列组合
        vector<bool> used(nums.size(),false);   //这个数组用来存储访问过的数组下标
        DFS(ret,nums,tmp,used); 
        return ret;    
    }
    void DFS(vector<vector<int> >&ret ,vector<int> &nums,vector<int> &tmp,vector<bool>& visited)    
    {
        if(tmp.size()==nums.size())   
        {
            ret.push_back(tmp);
            return ;
        }

/* 1 . 遍历nums中的每一个数并且递归到底
   2 . 递归返回后需要将刚刚访问过的下标中visited中删除, 这是为了下一种排列组合
  
  
*/
        for(int i=0;i<nums.size();i++)
        {
            if(visited[i])
            {
                 continue;
            }
            tmp.push_back(nums[i]);
            visited[i]=true;
            DFS(ret,nums,tmp,visited);
            visited[i]=false;
            tmp.pop_back();

        }
    }
};