LeetCode HOT 100 —— 49.全排列

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路

同代码随想录回溯算法 —— 全排列，一眼回溯，直接上

回溯三部曲：

1. 递归函数参数：排列是有序的，即[1,2] 和[2,1]是两个不同的集合，可以看到元素1在[1,2]中已经使用过了，但是在[2,1]中还要继续使用一次1，所以处理排列问题就不需要startIndex了
2. 递归终止条件：收集的叶子结点就是最终的结果，所以当到达叶子节点时，即path数组大小等于nums数组时，说明找到了一个全排列

if(path.size() == nums.length){
	result.add(path);
	return;
}
1
2
3
4

3. 单层搜索的逻辑：排列问题和之前的组合问题、切割问题、子集问题最大的不同就是for循环里面不需要使用startIndex了，因为排列问题每次都需要重头开始搜索

依旧是回溯模板：

result = []
backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10

java代码如下：

class Solution{
	public List<List<Integer>> permute(int[] nums){
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backTracking(res,path,nums);
		return res;
	}
	public void backTracking(List<List<Integer>> res, List<Integer> path, int[] nums){
		if(path.size() == nums.length){
			res.add(new ArrayList<>(path));
			return;
		}
		for(int num : nums){
            if(!path.contains(num)){
                path.add(num);
                backTracking(res,path,nums);
                path.remove(path.size() - 1);
            }
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21