示例-回溯排列

1、全排列

https://leetcode.cn/problems/permutations/
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<Integer> path = new ArrayList(nums.length);
HashSet<Integer> used = new HashSet(nums.length);
List<List<Integer>> res = new LinkedList<>();

    backTrace(res, path, used, nums);
    return res;
}

public void backTrace(List<List<Integer>> res, List<Integer> path, HashSet used
        , int[] nums) {
    if(path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    for(int i=0; i<nums.length; i++) {
        if(used.contains(nums[i])) {
            continue;
        }

        path.add(nums[i]);
        used.add(nums[i]);
        backTrace(res, path, used, nums);
        path.remove(path.size() -1);
        used.remove(nums[i]);
    }
}

}

2、全排列 II（原始数据有相同的）

https://leetcode.cn/problems/permutations-ii/
时间复杂度O(n×n!)

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

public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
    if (idx == nums.length) {
        ans.add(new ArrayList<Integer>(perm));
        return;
    }
    for (int i = 0; i < nums.length; ++i) {
        //因为重复元素只能按顺序出现vis[i - 1] = false
        if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
            continue;
        }
        perm.add(nums[i]);
        vis[i] = true;
        backtrack(nums, ans, idx + 1, perm);
        vis[i] = false;
        perm.remove(idx);
    }
}

}