1.排列(Permutations)

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

2.含有相同元素求排列

[1,1,2] have the following unique permutations:
[[1,1,2], [1,2,1], [2,1,1]]

数组元素可能含有相同的元素，进行排列时就有可能出现重复的排列，要求重复的排列只返回一个。
在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。
对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue;
}

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> permutes = new ArrayList<>();
    List<Integer> permuteList = new ArrayList<>();
    Arrays.sort(nums);  // 排序
    boolean[] hasVisited = new boolean[nums.length];
    backtracking(permuteList, permutes, hasVisited, nums);
    return permutes;
}

private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
    if (permuteList.size() == nums.length) {
        permutes.add(new ArrayList<>(permuteList));
        return;
    }

    for (int i = 0; i < visited.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
            continue;  // 防止重复
        }
        if (visited[i]){
            continue;
        }
        visited[i] = true;
        permuteList.add(nums[i]);
        backtracking(permuteList, permutes, visited, nums);
        permuteList.remove(permuteList.size() - 1);
        visited[i] = false;
    }
}