力扣46 全排列 java实现

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中的所有整数互不相同

该题是回溯问题 ，用递归较方便，每次只需要判断数组中的数是否被用过即可，即创建一个布尔数组来判别每个数组的位置是否被用过，接着按序递归遍历数组即可，只要保证保存的临时集合最大的个数要小于等于给定的数组个数，若等于数组个数则需要将其保存在结果集合中。具体代码如下：

public static void main(String[] args) { // 测试用 int[] nums = {1,2,3}; List<List<Integer>> res = permute(nums); for (List<Integer> list : res) { System.out.println(list); } } public static List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); helper(res, new ArrayList<>(), nums, 0, new boolean[nums.length]); return res; } public static void helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int count, boolean[] s){ if (count == nums.length){ res.add(new ArrayList<>(temp)); return; } if (count > nums.length){ return; } for (int i = 0; i < nums.length; i++) { if (s[i] == true){ continue; } temp.add(nums[i]); s[i] = true; helper(res, temp, nums, count + 1, s); temp.remove(temp.size() - 1);; s[i] = false; } }

以上为记录分享用，代码较差请见谅