（零）

广度优先遍历、回溯减枝、本质上都是树（决策树）的遍历。

Leetcode 46.全排列

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

示例:

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

分析：这道题有多种不同的算法，这里我利用bfs算法。
可以从数学上得全排列方法获得借鉴：
第一个数字选1，有多少中排列
第一个选2，有多少种排列
…
算法可以用一颗树来描述：

决策树的遍历

分析：树由叶子节点和非叶子节点组成。
1）如果当前节点是非叶子节点，就向下遍历。
2）如果当前是叶子节点，就对叶子节点进行判断，符合条件的就返回一个结果。（本题不需要对节点进行判断，我将在下一篇文章用到。）

public:vector<vector<int>> res;vector<vector<int>> permute(vector<int>& nums) {vector<int> pre;bfs(nums, pre);return res;}void bfs(vector<int> nums,vector<int> pre) {int n = nums.size();//到结尾的叶子节点,输出一个结果到res中if (n == 1) {		pre.push_back(nums[n-1]);res.push_back(pre);return;}//没到叶子节点，向下遍历for (int i = 0; i < n; i++) {vector<int> p(pre);	vector<int> s(nums);p.push_back(nums[i]);//当前元素加入到排列中s[i] = s[n-1];		 //删除当前元素s.pop_back();bfs(s, p);}}
};

决策树的算法并不复杂，但是大家最好自己动手，体会一下是如何遍历、如何停止、上下层信息如何传递。

声明

代码是我自己写到AC，但是上面的图片我看题解的时候拿的，原来是labuladong大佬的题解，他在github有一个几万star的算法学习项目，大家感兴趣的可以去看看。