LeetCode 46. 全排列（回溯演算法解決）

截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666

全排列也是一道經典的題，之前在講450，什么叫回溯演算法，一看就會，一寫就廢的時候，也提到過使用回溯演算法來解決，具體細節可以看下，假設陣列長度是n，我們可以把回溯演算法看做是一顆n叉樹的前序遍歷，第一層有n個子節點，第二層有n-1個子節點……，來看個視頻

視頻鏈接

代碼如下

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    //終止條件，如果數字都被使用完了，說明找到了一個排列，（可以把它看做是n叉樹到
    //葉子節點了，不能往下走了，所以要回傳）
    if (tempList.size() == nums.length) {
        //因為list是參考傳遞，這里必須要重新new一個
        list.add(new ArrayList<>(tempList));
        return;
    }
    //（可以把它看做是遍歷n叉樹每個節點的子節點）
    for (int i = 0; i < nums.length; i++) {
        //因為不能有重復的，所以有重復的就跳過
        if (tempList.contains(nums[i]))
            continue;
        //選擇當前值
        tempList.add(nums[i]);
        //遞回（可以把它看做遍歷子節點的子節點）
        backtrack(list, tempList, nums);
    }
}

我們就用陣列[1,2,3]來測驗一下，看一下列印結果

[1, 2, 3]

是不是很意外，示例1給出的是6個結果，這里列印的是1個，這是因為list是參考傳遞，當遍歷到葉子節點以后要往回走，往回走的時候必須把之前添加的值給移除了，否則會越加越多，我們來看下視頻
視頻鏈接

再來看下代碼

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    //終止條件，如果數字都被使用完了，說明找到了一個排列，（可以把它看做是n叉樹到
    //葉子節點了，不能往下走了，所以要回傳）
    if (tempList.size() == nums.length) {
        //因為list是參考傳遞，這里必須要重新new一個
        list.add(new ArrayList<>(tempList));
        return;
    }
    //（可以把它看做是遍歷n叉樹每個節點的子節點）
    for (int i = 0; i < nums.length; i++) {
        //因為不能有重復的，所以有重復的就跳過
        if (tempList.contains(nums[i]))
            continue;
        //選擇當前值
        tempList.add(nums[i]);
        //遞回（可以把它看做遍歷子節點的子節點）
        backtrack(list, tempList, nums);
        //撤銷選擇，把最后一次添加的值給移除
        tempList.remove(tempList.size() - 1);
    }
}

我們來看一下運行結果

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

這題使用回溯演算法的還一種解決方式就是交換，比如我們先選擇第一個數字，然后和后面的所有數字都交換一遍，這樣全排列的第一位就確定了，然后第二個數字在和后面的所有數字交換一遍，這樣全排列的第二位數字也確定了……，一直繼續下去，直到最后一個數字不能交換為止，這里畫個圖來看一下

來看下代碼

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, res);
    return res;
}

public void backtrack(int[] nums, int index, List<List<Integer>> res) {
    //到最后一個數字，沒法再交換了，直接把陣列轉化為list
    if (index == nums.length - 1) {
        //把陣列轉為list
        List<Integer> tempList = new ArrayList<>();
        for (int num : nums)
            tempList.add(num);
        //把list加入到res中
        res.add(tempList);
        return;
    }
    for (int i = index; i < nums.length; i++) {
        //但前數字nums[index]要和后面所有的數字都要交換一遍（包括
        // 他自己）
        swap(nums, index, i);
        //遞回，陣列[0,index]默認是已經排列好的，然后從index+1開始
        //后面元素的交換
        backtrack(nums, index + 1, res);
        //還原回來
        swap(nums, index, i);
    }
}

//交換兩個數字的值
private void swap(int[] nums, int i, int j) {
    if (i != j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

遞回解決

我們來思考這樣一個問題，假如陣列[1,2,3]，我們知道了[2,3]的全排列結果，只需要把1放到這些全排列的所有位置，即是陣列[1,2,3]的全排列，畫個圖來看一下

//遞回解決
public List<List<Integer>> permute(int[] nums) {
    return helper(nums, 0);
}

/**
 * @param nums
 * @param index 遞回當前數字的下標
 * @return
 */
private List<List<Integer>> helper(int[] nums, int index) {
    List<List<Integer>> res = new ArrayList<>();
    //遞回的終止條件，如果到最后一個陣列，直接把它放到res中
    if (index == nums.length - 1) {
        //創建一個臨時陣列
        List<Integer> temp = new ArrayList<>();
        //把數字nums[index]加入到臨時陣列中
        temp.add(nums[index]);
        res.add(temp);
        return res;
    }
    //計算后面數字的全排列
    List<List<Integer>> subList = helper(nums, index + 1);
    //集合中每個子集的長度
    int count = subList.get(0).size();
    //遍歷集合subList的子集
    for (int i = 0, size = subList.size(); i < size; i++) {
        //把當前數字nums[index]添加到子集的每一個位置
        for (int j = 0; j <= count; j++) {
            List<Integer> temp = new ArrayList<>(subList.get(i));
            temp.add(j, nums[index]);
            res.add(temp);
        }
    }
    return res;
}