剑指 Offer 38. 字符串的排列

回溯：决策当前字符串的某一位填入什么字符。
去重通用方法：

• 使用 Set 实现去重；
• 先对原字符串进行排序，然后确保相同字符传入同一目标位置的动作只发生一次。

方法一： Set 去重

只对结果去重，没有去除重复计算。42 ms

class Solution {
    
    Set<String> set = new HashSet<>();
    char[] arr;
    boolean[] vis;
    public String[] permutation(String s) {
    
        arr = s.toCharArray();
        vis = new boolean[arr.length];
        backtrack(0, "");
        return set.toArray(String[]::new);
    }
    void backtrack(int idx, String t){
    
        if(idx == arr.length) {
    
            set.add(t);
            return;
        }
        for(int i = 0; i < arr.length; i++){
    
            if(vis[i]) continue;
            vis[i] = true;
            backtrack(idx + 1, t + arr[i]);
            vis[i] = false; // 回溯
        }
    }
}

逐位去重 21 ms

class Solution {
    
    List<String> list = new ArrayList<>();
    char[] arr;
    boolean[] vis;
    public String[] permutation(String s) {
    
        arr = s.toCharArray();
        vis = new boolean[arr.length];
        backtrack(0, "");
        return list.toArray(String[]::new);
    }
    void backtrack(int idx, String t){
    
        if(idx == arr.length) {
    
            list.add(t);
            return;
        }
        Set<Character> set = new HashSet<>(); // 去重
        for(int i = 0; i < arr.length; i++){
    
            if(vis[i] || set.contains(arr[i])) continue;
            vis[i] = true;
            set.add(arr[i]);
            backtrack(idx + 1, t + arr[i]);
            vis[i] = false;
        }
    }
}

通过交换遍历 6 ms

class Solution {
    
    List<String> list = new ArrayList<>();
    char[] arr;    
    public String[] permutation(String s) {
    
        arr = s.toCharArray();        
        backtrack(0);
        return list.toArray(String[]::new);
    }
    void backtrack(int idx){
    
        if(idx == arr.length - 1) {
    
            list.add(new String(arr)); // String.valueOf(arr)
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i = idx; i < arr.length; i++){
    
            if(set.contains(arr[i])) continue;
            set.add(arr[i]);
            swap(i, idx);  // 当前位分别替换成后面的其它字母
            backtrack(idx + 1);
            swap(idx, i);
        }
    }
    void swap(int i, int j){
    
        char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

方法二：排序去重

class Solution {
    
    List<String> list = new ArrayList<>();
    char[] arr;    
    boolean[] vis;
    public String[] permutation(String s) {
    
        arr = s.toCharArray();  
        vis = new boolean[arr.length];
        Arrays.sort(arr);      
        backtrack(0, "");
        return list.toArray(String[]::new);
    }
    void backtrack(int idx, String t){
    
        if(idx == arr.length) {
    
            list.add(t); 
            return;
        }        
        for(int i = 0; i < arr.length; i++){
    
            if(vis[i] || i > 0 && !vis[i-1] && arr[i] == arr[i-1]) continue;
            vis[i] = true;            
            backtrack(idx + 1, t + String.valueOf(arr[i]));
            vis[i] = false;
        }
    }
}

47.全排列II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        def backtrack(depth=0, path=[]):
            if depth == n: 
                res.append(path[:])
                return
            for i in range(n):               
                if used[i] or (i > 0 and nums[i] == nums[i - 1] and used[i - 1]): continue
                
                path.append(nums[i])
                used[i] = True
                backtrack(depth + 1, path)
                path.pop()
                used[i] = False

        def backtrack1(depth=0):
            if depth == n: res.append(nums[:])              
            for i in range(depth, n):
                nums[depth], nums[i] = nums[i], nums[depth]
                backtrack1(depth + 1)
                nums[depth], nums[i] = nums[i], nums[depth]

        ## 深度优先搜索
        def dfs(depth=0, path=[], tmp=nums):
            if depth == n:
                res.append(path)
                return
            for i in range(len(tmp)):
                dfs(depth + 1, path + [tmp[i]], tmp[:i] + tmp[i + 1:])
        
        n, res = len(nums), []  
        nums.sort() 
        used = [False] * n
        backtrack()
        # backtrack1()
        # dfs()

        return res
        # return list(set(permutations(nums)))

class Solution {
    
    boolean[] vis;
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> perm = new ArrayList<Integer>();

    public List<List<Integer>> permuteUnique(int[] nums) {
    
        vis = new boolean[nums.length];
        Arrays.sort(arr);
        backtrack(0, nums);
        return ans;
    }

    public void backtrack(int idx, int[] arr){
    
        if (idx == arr.length) {
    
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < arr.length; ++i) {
    
            if (vis[i] || i > 0 && arr[i] == arr[i-1] && !vis[i-1]) continue;  // !used[i-1] 比 used[i-1] 快点
            perm.add(arr[i]);
            vis[i] = true;
            backtrack(idx + 1, arr);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

class Solution {
    
    List<List<Integer>> ans;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        ans = new LinkedList<>();
        backtrack(0, nums);
        return ans;
    }

    void backtrack(int idx, int[] arr) {
    
        if (idx == arr.length) {
    
            // ans.add(Arrays.stream(arr).boxed().toList());
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < arr.length; i++) tmp.add(arr[i]);
            ans.add(tmp);
            return;
        }
        Set<Integer> set = new HashSet<>();
        for (int j = idx; j < arr.length; j++) {
    
            if (!set.contains(arr[j])) {
    
                set.add(arr[j]);
                swap(arr, j, idx);
                backtrack(idx + 1, arr);
                swap(arr, j, idx);
            }
        }
    }

    void swap(int[] nums, int i, int j) {
    
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}

方法三：31. 下一个排列

class Solution {
    
    public String[] permutation(String s) {
    
        List<String> ans = new ArrayList<String>();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        do {
    
            ans.add(new String(arr));
        } while (nextPermutation(arr));
        
        return ans.toArray(String[]::new);
    }

    boolean nextPermutation(char[] arr) {
    
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;
        int j = arr.length - 1;
        while (j >= 0 && arr[i] >= arr[j]) j--;
        swap(arr, i, j);
        reverse(arr, i + 1);
        return true;
    }

    void swap(char[] arr, int i, int j) {
    
        char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }

    void reverse(char[] arr, int left) {
    
        int right = arr.length - 1;
        while (left < right) {
    
            swap(arr, left++, right--);
        }
    }
}

31. 下一个排列

class Solution {
    
    public void nextPermutation(int[] nums) {
    
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0){
    
            reverse(nums, 0);
            return;
        } 
        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) j--;
        swap(nums, i, j);
        reverse(nums, i + 1);
        return;
    }

    void swap(int[] arr, int i, int j) {
    
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }

    void reverse(int[] arr, int left) {
    
        int right = arr.length - 1;
        while (left < right) {
    
            swap(arr, left++, right--);
        }
    }
}