Permutation

Find all => DFS，思路為每次找到以某個元素為開頭，再去遍歷所有其他元素，

所以會遇到又要把自己加進去的情況，我們可以開一個 isVisited array or set(沒重複可以用set) 來避免

[1,2,3] : [1] -> [1,2] -> [1, 2, 3] (第一層結束) ==> backtrack [1] (下一個為3) -> [1, 3] -> [1, 3, 2]

public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> results = new ArrayList<>();
    if (nums == null) {
        return results;
    }
    if (nums.length == 0) {
        results.add(new ArrayList<Integer>());
        return results;
    }

    boolean[] isVisited = new boolean[nums.length];
    for (int i = 0; i < nums.length; i++) {
        isVisited[i] = false;
    }
    helper(nums, isVisited, new ArrayList<Integer>(), results);
    return results;
}

public void helper(int[] nums, 
                    boolean[] visited, 
                    List<Integer> permutation,
                    List<List<Integer>> results) {
    //end
    if (permutation.size() == nums.length) {
        results.add(new ArrayList<Integer>(permutation));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (visited[i] == false) {
            permutation.add(nums[i]);
            visited[i] = true;
            helper(nums, visited, permutation, results);
            permutation.remove(permutation.size() - 1);
            visited[i] = false;
        }
    }
    return;
}

permutation II 則是要在有重複元素的情況下

那麼跟前面都相同，我們要確保在前面的要先被挑到

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