剑指 Offer II 083. 没有重复元素集合的全排列

没有重复元素的全排列

1. 需要使用一个 boolean[] visited 表示该元素是否已经被访问过。

2. for 循环遍历一直需要从 0 开始。

   class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        res = new ArrayList<>();
        // 全排列
        int len = nums.length;
        boolean[] visited = new boolean[len];
        List<Integer> path = new ArrayList<>();
        backTracking(nums, 0, len, path, visited);
        return res;
    }
    private void backTracking(int[] nums, int pos, int len, List<Integer> path, boolean[] visited) {
        if (path.size() == len) {
            // collect
            res.add(new ArrayList<>(path));
            return ;
        }
        for (int i = 0; i < len; i++) {
            if (visited[i]) continue;
            path.add(nums[i]);
            visited[i] = true;
            backTracking(nums, i + 1, len, path, visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
   }