題目：給定一個 沒有重複 數字的序列，返回其所有可能的全排列。

標籤：回溯演算法

示例：

輸入: [1,2,3]

輸出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

我的思路： 該題目標籤是一個回溯演算法。回溯演算法的題目型別大概包括全排列、子集、組合等。這些型別的題目都可以使用回溯演算法的思路去求解，大體框架一樣。那麼該題目我們的解答如下。

1.使用一個集合來去重。

public static List<List<Integer>> permute3(int[] nums) {        List<List<Integer>> res = new ArrayList<List<Integer>>();        backTraver3(nums, new LinkedList<>() , res);        return res;    } public static void backTraver3(int[] nums, LinkedList<Integer> pick, List<List<Integer>> res) {        if (pick.size() == nums.length) {            res.add(new ArrayList<>(pick));            return;        }        for (int i = 0; i < nums.length; i++) {            if (pick.contains(nums[i])) continue;            pick.add(nums[i]);            backTraver3(nums, pick, res);            pick.removeLast();        }    }

2.使用Boolean陣列來標識元素是否使用

 public static List<List<Integer>> permute4(int[] nums) {        List<List<Integer>> res = new ArrayList<List<Integer>>();        LinkedList<Integer> pick = new LinkedList<>();        boolean[] used = new boolean[nums.length];        backTraver5(nums, used, pick, res);        return res;    }    public static void backTraver5(int[] nums, boolean[] used, LinkedList<Integer> pick, List<List<Integer>> res) {        if (pick.size() == nums.length) {            res.add(new ArrayList<>(pick));            return;        }        for (int i = 0; i < nums.length; i++) {            if (used[i] == true) {                continue;            }            //開始選擇            pick.addLast(nums[i]);            used[i] = true;            //選擇判斷            backTraver5(nums, used, pick, res);            //選擇復位            used[i] = false;            pick.removeLast();        }    }

3.假設nums[]陣列索引cur之前的元素已經排列好了。 那麼我們只用排序cur索引後的資料就行。

public List<List<Integer>> permute2(int[] nums) {        List<List<Integer>> res = new ArrayList<List<Integer>>();        List<Integer> list = new ArrayList<>();        for (int i : nums) {            list.add(i);        }        backTraver2(0, list, res);        return res;    }    public static void backTraver2(int cur, List<Integer> nums, List<List<Integer>> res) {        if (cur == nums.size()) {            res.add(new ArrayList<>(nums));        }        for (int i = cur; i < nums.size(); i++) {            Collections.swap(nums, cur, i);            backTraver2(cur + 1, nums, res);            Collections.swap(nums, i, cur);        }    }

該題目是一個標準的回溯演算法題目，我們可以學一下回溯演算法的框架。