回溯算法——排列篇

目录

一、全排列

二、全排列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;
            }
        }
    }
}