回溯算法——分列篇

目录
一、全分列
二、全分列II

---

一、全分列

46. 全分列 - 力扣（LeetCode）

1. class Solution {
2.     List<List<Integer>> result=new ArrayList<>();
3.     LinkedList<Integer> path=new LinkedList<>();
4.     boolean[] used;
5.     public List<List<Integer>> permute(int[] nums) {
6.         used=new boolean[nums.length];
7.         backtracking(nums);
8.         return result;
9.     }
10.     public void backtracking(int[] nums){
11.         if(path.size()==nums.length){
12.             result.add(new ArrayList<>(path));
13.             return;
14.         }
15.         for(int i=0;i<nums.length;i++){
16.             if(used[i])continue;
17.             used[i]=true;
18.             path.add(nums[i]);
19.             backtracking(nums);
20.             path.removeLast();//移除最后一个添加的元素
21.             used[i]=false;//元素修改为未使用
22.         }
23.     }
24. }

复制代码

二、全分列II

47. 全分列 II - 力扣（LeetCode）

1. class Solution {
2.     List<List<Integer>> result=new ArrayList<>();
3.     List<Integer> path=new ArrayList<>();
4.     public List<List<Integer>> permuteUnique(int[] nums) {
5.         boolean[] used=new boolean[nums.length];
6.         Arrays.fill(used,false);
7.         Arrays.sort(nums);
8.         backtracking(nums,used);
9.         return result;
10.     }
11.     public void backtracking(int[] nums,boolean[] used){
12.         if(path.size()==nums.length){
13.             result.add(new ArrayList<>(path));
14.             return;
15.         }
16.         for(int i=0;i<nums.length;i++){
17.             if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true)continue;
18.             if(used[i]==false){
19.                 used[i]=true;
20.                 path.add(nums[i]);
21.                 backtracking(nums,used);
22.                 path.removeLast();
23.                 used[i]=false;
24.             }
25.         }
26.     }
27. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。