【Hot100】LeetCode—46. 全排列

本文主要是介绍【Hot100】LeetCode—46. 全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

• 题目连接：46. 全排列

---

1- 思路

回溯

• 由于是排列问题，需要讲究元素顺序。元素相同顺序不同是不同的排列，而组合问题不强调元素顺序。
• 组合中的 startIndex 是用来保证，不会出现 [1,2] [2,1] 的情况，因此本题是排列，需要 [1,2] [2,1] 的情况，所以是有必要的。

回溯三部曲

• 1. 终止条件
  • 结果长度为 数组长度的时候，收集结果到 res 中
• 2. 回溯逻辑，需要用 used 数组去重

---

2- 实现

⭐46. 全排列——题解思路

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];Arrays.fill(used,false);backTracing(nums);return res;}public  void backTracing(int[] nums){// 终止条件if(path.size() == nums.length){res.add(new ArrayList(path));return ;}// 遍历// 树宽 for(int i = 0;i<nums.length;i++){if(used[i]){continue;}used[i] = true;path.add(nums[i]);backTracing(nums);path.remove(path.size()-1);used[i] = false;}}
}

---

3- ACM 实现

public class permute {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];Arrays.fill(used,false);backTracing(nums);return res;}public  void backTracing(int[] nums){// 终止条件if(path.size() == nums.length){res.add(new ArrayList(path));return ;}// 遍历// 树宽for(int i = 0;i<nums.length;i++){if(used[i]){continue;}used[i] = true;path.add(nums[i]);backTracing(nums);path.remove(path.size()-1);used[i] = false;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}permute p = new permute();List<List<Integer>> result = p.permute(nums);System.out.println("结果是"+result.toString());}
}

这篇关于【Hot100】LeetCode—46. 全排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---