leetcode47

清疚 2021-12-19 04:15 152阅读 0赞

1 public class Solution {
     2     public List<List<Integer>> permuteUnique(int[] nums) {
     3         List<List<Integer>> permutes = new ArrayList<>();
     4         List<Integer> permuteList = new ArrayList<>();
     5         Arrays.sort(nums);  // 排序
     6         boolean[] hasVisited = new boolean[nums.length];
     7         backtracking(permuteList, permutes, hasVisited, nums);
     8         return permutes;
     9     }
    10 
    11     private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
    12         if (permuteList.size() == nums.length) {
    13             permutes.add(new ArrayList<>(permuteList));
    14             return;
    15         }
    16 
    17         for (int i = 0; i < visited.length; i++) {
    18             if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { 19                 continue;  // 防止重复
    20 } 21             if (visited[i]){
    22                 continue;
    23             }
    24             visited[i] = true;
    25             permuteList.add(nums[i]);
    26             backtracking(permuteList, permutes, visited, nums);
    27             permuteList.remove(permuteList.size() - 1);
    28             visited[i] = false;
    29         }
    30     }
    31 }

对比[leetcode46][]：

1 public class LEET_46 {
     2     public List<List<Integer>> permute(int[] nums) {
     3         List<List<Integer>> permutes = new ArrayList<>();
     4         List<Integer> permuteList = new ArrayList<>();
     5         boolean[] hasVisited = new boolean[nums.length];
     6         backtracking(permuteList, permutes, hasVisited, nums);
     7         return permutes;
     8     }
     9 
    10     private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
    11         if (permuteList.size() == nums.length) {
    12             permutes.add(new ArrayList<>(permuteList)); // 重新构造一个 List
    13             return;
    14         }
    15         for (int i = 0; i < visited.length; i++) {
    16             if (visited[i]) {
    17                 continue;
    18             }
    19             visited[i] = true;
    20             permuteList.add(nums[i]);
    21             backtracking(permuteList, permutes, visited, nums);
    22             permuteList.remove(permuteList.size() - 1);
    23             visited[i] = false;
    24         }
    25     }
    26 }

转载于:https://www.cnblogs.com/asenyang/p/10997891.html

[leetcode46]: https://www.cnblogs.com/asenyang/p/6970281.html