Java回溯法解决全排列问题流程详解

    // 用于存储结果的数组
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backTrack(nums, list, used);
        return ans;
    }
    // 回溯法参数： nums为待排列数组， list存储当前排列结果， used[]标记当前元素是否被使用过
    public void backTrack(int[] nums, List<Integer> list, boolean[] used){
        // 回溯法退出条件，list大小为nums[]长度，即所有元素都已加入排列
        if(list.size() == nums.length){
            // 加入结果数组，注意要 new 新的list (List为按指针所指地址存储，不然每次加的都是同一个)
            ans.add(new ArrayList(list));
            return;
        }
        // 循环以每个元素开始排列
        for(int i=0; i<nums.length; i++){
            // 元素未被使用过加入排列
            if(!used[i]){
                // 在排列中加入当前元素，并将used[i]修改为true
                list.add(nums[i]);
                used[i] = true;
                // 递归调用 backTrack
                backTrack(nums, list, used);
                // 回溯，去掉当前元素，并将used置为false
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }

class Solution {
    Boolean[] visit;
    List<List<Integer>> ans;
    public List<List<Integer>> permuteUnique(int[] nums) {
        visit = new Boolean[nums.length];
        Arrays.fill(visit, false);
        List<Integer> list = new ArrayList<>();
        ans = new ArrayList<>();
        Arrays.sort(nums);
        backTrack(nums, list);
        return ans;
    }
    public void backTrack(int[] nums, List<Integer> list){
        if(nums.length == list.size()){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i=0; i<nums.length; i++){
            // 当前元素用过 + 限制每轮填入的字符都是重复字符的从左到右的第一个字符
            if(visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1])){
                continue;
             }
            list.add(nums[i]);
            visit[i] = true;
            backTrack(nums, list);
            visit[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

class Solution {
    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        // 思路： 回溯法典型例题 —— 含重复问题
        char[] array = s.toCharArray();
        Arrays.sort(array);
        Boolean[] used = new Boolean[array.length];
        Arrays.fill(used, false);
        backTack(array, used, new StringBuilder());
        String[] res = new String[ans.size()];
        for(int i=0; i<ans.size(); i++){
            res[i] = ans.get(i);
        }
        return res;
    }
    public void backTack(char[] array, Boolean[] used, StringBuilder sb){
        if(array.length == sb.length()){
            ans.add(new String(sb));
        }
        for(int i=0; i<array.length; i++){
           if(used[i]){
               continue;
           }
           if(i>0 && array[i]==array[i-1] && !used[i-1]){
               continue;
           }
            sb.append(array[i]);
            used[i] = true;
            backTack(array, used, sb);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}