全排列
- 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
- 输入：nums = [1,2,3]
- 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
-
示例 2：
- 输入：nums = [0,1]
- 输出：[[0,1],[1,0]]
-
示例 3：
- 输入：nums = [1]
- 输出：[[1]]
提示：
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- nums 中的所有整数 互不相同
思考
- 这是典型的回溯算法问题。因为求排列组合,需要一步一步递归构建所有可能的排列。
- 关键是要理解回溯算法的思想 - 路径的选择和回退。要不断地选择,递归探索下一个可能的分支,再退回到上一步,探索其他分支。
- 需要定义递归函数,作为回溯函数,传入当前的 intermediate path。
- 终止条件是路径长度等于数组长度,说明找到了一个全排列。
- 在递归函数内部,需要遍历数组,选择一个数字加入路径,递归调用,然后再删除以回退。
- 需要剪枝,也就是重复元素的去重处理。
- 需要一个结果 list 来保存找到的所有排列,在终止时addToList。
题解
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
// 定义回溯方法
backtrack(nums, new ArrayList<>(), res);
return res;
}
// 回溯算法
private void backtrack(int[] nums, List<Integer> tempList, List<List<Integer>> res) {
// 路径长度等于数组长度时,找到一种排列
if(tempList.size() == nums.length) {
res.add(new ArrayList<>(tempList));
return;
}
// 遍历数组中的每个元素作为路径元素
for(int n : nums) {
// 如果元素已存在路径中,跳过
if(tempList.contains(n)) continue;
// 添加元素到路径
tempList.add(n);
// 回溯
backtrack(nums, tempList, res);
// 回溯后删除元素
tempList.remove(tempList.size() - 1);
}
}
}