[数据结构与算法]含有重复元素的全排列java实现

class Solution {
    public String[] permutation(String S) {
        int length = 1;
        for(int i = 1;i <= S.length();i++){
            length *= i;
        }
        //准备结果集
        LinkedList<String> result = new LinkedList<>();
        //递归
        backcheck(S.toCharArray(),0,result);
        //返回结果
        
        return result.toArray(new String[0]);
    }

    public void backcheck(char[] nums,int index,LinkedList<String> result){
        //设置递归出口
        if(index == nums.length){
            //这时的nums是一种排列，需要添加到结果集中
            result.add(new String(nums));
        }else{
            //对于本位置遍历所有的可能性
            //创建一个set来避免重复判断，
            HashSet<Character> set = new HashSet<>();
            for(int i = index;i < nums.length;i++){
                //每次开始递归之前判断本元素是否已经遍历
                if(!set.contains(nums[i])){
                    //加入set标志本数已经遍历过
                    set.add(nums[i]);
                    //替换本位置表示本位置的数确定下来
                    swap(nums,index,i);
                    //接着下一个位置的判断
                    backcheck(nums,index + 1,result);
                    //判断结束后需要复位接着本位置下一个结果的判断
                    swap(nums,index,i);
                }
            }
        }
    }

    public void swap(char nums[],int i,int j){
        if(i != j){
            char temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp; 
        }
    }
}