LeetCode--46.全排列（回溯算法）

46.全排列

题目描述

给定一个不含重复数字的数组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中的所有整数互不相同

代码

classSolution{// 存放所有排列结果List<List<Integer>>result=newArrayList<>();// 当前路径（当前排列）List<Integer>path=newArrayList<>();/** * 回溯函数 * * @param nums 原数组 * @param used used[i] 表示 nums[i] 是否已经被使用 */publicvoidbacktracking(int[]nums,int[]used){/** * 终止条件 * * 当当前路径长度等于数组长度时， * 说明已经形成一个完整排列 */if(path.size()==nums.length){// 加入结果集result.add(newArrayList<>(path));return;}/** * 全排列： * 每一层都要从 0 开始遍历 * * 因为： * 每个位置都可以放任意未使用元素 */for(inti=0;i<nums.length;i++){/** * 如果当前元素没有被使用 */if(used[i]==0){// 做选择：加入当前元素path.add(nums[i]);// 标记当前元素已使用used[i]=1;// 递归下一层backtracking(nums,used);// 回溯：恢复现场// 当前元素恢复未使用状态used[i]=0;// 删除路径最后一个元素path.remove(path.size()-1);}}}publicList<List<Integer>>permute(int[]nums){/** * used数组： * * used[i] == 1 * 表示 nums[i] 已经在当前路径中 * * used[i] == 0 * 表示 nums[i] 还未使用 */int[]used=newint[nums.length];backtracking(nums,used);returnresult;}}