题目描述
给定一个不含重复数字的数组 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 中的所有整数 互不相同
题目解析
- 全排列问题
- 根据题意，需要求得所有的排列可能，如下图
- 把每一种可能加入到结果集中，最终得到答案
- 由于选择过的元素不能重复使用，所以需要额外记录当前元素是否被选择使用过
show code
class Solution {
private List<List<Integer>> ans;
public List<List<Integer>> permute(int[] nums) {
ans = new ArrayList<>();
// 创建一个数组，记录被选择过的元素
boolean[] used = new boolean[nums.length];
// 创建一个 集合 用于保存被选择的元素
List<Integer> chosed = new ArrayList<>();
// 进入回溯算法
bt(nums, used, chosed);
return ans;
}
private void bt(int[] nums, boolean[] used, List<Integer> chosed) {
// 终止条件 如果选择的元素个数 等于 数组长度
if(nums.length == chosed.size()) {
// 加入到结果集合中
ans.add(new ArrayList<>(chosed));
return;
}
// 遍历 nums 数组
for(int i = 0;i < nums.length;i++) {
if(used[i]) {
// 如果被选择过了，跳过.
continue;
}
// 选择当前元素
chosed.add(nums[i]);
// 标记选择
used[i] = true;
// 回溯
bt(nums, used, chosed);
// 移出集合
chosed.remove(chosed.size() - 1);
// 取消标记
used[i] = false;
}
}
}