题目

image.png

思路

  • 思路：使用回溯来选择不同的分支以达到排列结果，但是如何知道那些结果已经使用过，就需要一个数组记录已使用的数据

    代码

    1.   List<List<Integer>> res = new ArrayList<>();
    2.   public List<List<Integer>> permute(int[] nums) {
    3.       boolean[] visited = new boolean[nums.length];
    4.       recur(new ArrayList<>(), visited, nums);
    5.       return res;
    6.   }
    8.   public void recur(List<Integer> cur, boolean[] visited, int[] nums) {
    9.       if (cur.size() == nums.length) {
    10.           res.add(cur);
    11.           return;
    12.       }
    13.       for (int i = 0; i < nums.length; i++) {
    14.           if (!visited[i]) {
    15.               visited[i] = true;
    16.               List<Integer> list = new ArrayList<>(cur);
    17.               list.add(nums[i]);
    18.               recur(list, visited, nums);
    19.               visited[i] = false;
    20.           }
    21.       }
    22.   }
    24.   //修改一下写法
    25.   public List<List<Integer>> permute(int[] nums) {
    26.       List<List<Integer>> res = new ArrayList<>();
    27.       recur(res, new ArrayList<>(), nums);
    28.       return res;
    29.   }
    31.   public void recur(List<List<Integer>> res, List<Integer> cur, int[] nums) {
    32.       if (cur.size() == nums.length) {
    33.           res.add(new ArrayList<>(cur));
    34.           return;
    35.       }
    36.       for (int i = 0; i < nums.length; i++) {
    37.           if (nums[i] == Integer.MAX_VALUE) continue;
    38.           cur.add(nums[i]);
    39.           nums[i] = Integer.MAX_VALUE;
    40.           recur(res, cur, nums);
    41.           nums[i] = cur.remove(cur.size() - 1);
    42.       }
    43.   }

    全排列