力扣题目链接:https://leetcode-cn.com/problems/permutations/
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
此时我们已经学习了77.组合问题、 131.分割回文串和78.子集问题,接下来看一看排列问题。
相信这个排列问题就算是让你用for循环暴力把结果搜索出来,这个暴力也不是很好写。
所以正如我们在关于回溯算法,你该了解这些!所讲的为什么回溯法是暴力搜索,效率这么低,还要用它?
因为一些问题能暴力搜出来就已经很不错了!
我以[1,2,3]为例,抽象成树形结构如下:
46.全排列
首先排列是有序的,也就是说[1,2] 和[2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组,标记已经选择的元素,如图橘黄色部分所示:
46.全排列
代码如下:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)
46.全排列
可以看出叶子节点,就是收割结果的地方。
那么什么时候,算是到达叶子节点呢?
当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。
代码如下:
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
这里和77.组合问题、131.切割问题和78.子集问题最大的不同就是for循环里不用startIndex了。
因为排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。
而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次。
代码如下:
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素,直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
整体C++代码如下:
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素,直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
大家此时可以感受出排列问题的不同:
排列问题是回溯算法解决的经典题目,大家可以好好体会体会。
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0){
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int[] nums){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
if (used[i]){
continue;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = [] #存放符合条件结果的集合
path = [] #用来存放符合条件的结果
used = [] #用来存放已经用过的数字
def backtrack(nums,used):
if len(path) == len(nums):
return res.append(path[:]) #此时说明找到了一组
for i in range(0,len(nums)):
if nums[i] in used:
continue #used里已经收录的元素,直接跳过
path.append(nums[i])
used.append(nums[i])
backtrack(nums,used)
used.pop()
path.pop()
backtrack(nums,used)
return res
var res [][]int
func permute(nums []int) [][]int {
res = [][]int{}
backTrack(nums,len(nums),[]int{})
return res
}
func backTrack(nums []int,numsLen int,path []int) {
if len(nums)==0{
p:=make([]int,len(path))
copy(p,path)
res = append(res,p)
}
for i:=0;i<numsLen;i++{
cur:=nums[i]
path = append(path,cur)
nums = append(nums[:i],nums[i+1:]...)//直接使用切片
backTrack(nums,len(nums),path)
nums = append(nums[:i],append([]int{cur},nums[i:]...)...)//回溯的时候切片也要复原,元素位置不能变
path = path[:len(path)-1]
}
}
旧文链接:回溯算法:排列问题!
-------------end------------