回溯算法——排列篇

目录

一、全排列

二、全排列II

一、全排列

46. 全排列 - 力扣（LeetCode）

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {used=new boolean[nums.length];backtracking(nums);return result;}public void backtracking(int[] nums){if(path.size()==nums.length){result.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){if(used[i])continue;used[i]=true;path.add(nums[i]);backtracking(nums);path.removeLast();//移除最后一个添加的元素used[i]=false;//元素修改为未使用}}
}

二、全排列II

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

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used=new boolean[nums.length];Arrays.fill(used,false);Arrays.sort(nums);backtracking(nums,used);return result;}public void backtracking(int[] nums,boolean[] used){if(path.size()==nums.length){result.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true)continue;if(used[i]==false){used[i]=true;path.add(nums[i]);backtracking(nums,used);path.removeLast();used[i]=false;}}}
}