子序列與全排列的區別？

可能大家聽到這兩個名詞，似乎感覺有點相似，分不清楚，什么是子序列，什么是全排列，本期文章就來給大家捋清楚這兩個是什么，Let’s go.

三道題：

1. 列印一個字串的全部子序列，包括空字串，
2. 給定一個不含重復數字的陣列 nums ，回傳其 所有可能的全排列 ，你可以 按任意順序 回傳答案，鏈接
3. 給定一個可包含重復數字的序列 nums ，按任意順序 回傳所有不重復的全排列，鏈接

本期文章原始碼：GitHub

一、列印全部的子序列

列印一個字串的全部子序列，包括空字串，

解題之前，我們先來看看什么是子序列， 所謂子序列就是：抽取原字串的一些字符，按照原字串的順序進行放置的新字串，舉個例子：

原字串為abcde，它的子序列可能是abc、abce、bcde等等； 分解子序列三個字的意思是：1、一定是原字串的一些字符，2、一定是有序的（原字串是什么先后順序，新字串也是什么先后順序），

那怎么進行解題呢？我們不妨看下圖：

理解了大致的思路，我們能夠做出兩種選擇，那就是要和不要當前這個字符，現在我們來看代碼

//方法一
//str，是呼叫這個方法時，直接通過字串轉化過來的
//i， 表示 當前在str陣列的位置
//list， 是存放所有的子序列的
public void getSubsequence1(char[] str, int i, ArrayList<String> list) {
    if (i == str.length) {
        list.add(str.toString()); //轉換為字串，存盤即可
    }
    getSubsequence(str, i + 1, list); //表示  要了當前位置的字符
    char tmp = str[i]; //臨時存盤字符
    str[i] = '\0'; //將該位置的字符改為\0
    
    getSubsequence(str, i + 1, list); //不要當前的字符
    str[i] = tmp; //恢復原來的樣子
}

//方法二
//res  是本次回圈的一次結果，最后將這個結果放入list里面
public static void getSubsequence2(char[] str, int i, ArrayList<String> list, StringBuilder res) {
    if (i == str.length) {
        list.add(res.toString());
        return;
    }

    res.append(str[i]); //要當前字符
    getSubsequence2(str, i + 1, list, res);

    res.delete(res.length() - 1, res.length()); //不要當前字符
    getSubsequence2(str, i + 1, list, res);

}

上面兩組代碼都大同小異，整體是時間復雜度差不多，只是方法二需要的空間稍微多一點點，差別就在這，看大家覺得那種方法更好了！！！

二、無重復值的全排列

LeetCode鏈接

全排列：從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列，當m=n時所有的排列情況叫全排列，

也就是說，給定一個字串，每個字符，可以隨便放在字串的哪一個位置，這樣組合起來的字串，就是排列的，對比子序列來說，子序列的字符出現順序，需要跟原字符出現的先后順序一樣，這也是二者的區別所在，

舉例子：

至于如何表示剩下的字符，以及如何選擇字符，我們來看代碼，就能夠理解了！！！

public List<List<Integer>> permute(int[] nums) {
    if (nums == null) {
        return null;
    }
    List<List<Integer>> res = new ArrayList<>();
    getFullPermute(nums, 0, res); //遞回呼叫子程序
    return res;
}

//nums， 是所有的資料，
//nums[0 ... i - 1] 范圍內，是已經確定好的資料
//nums[i...] 范圍上的資料，就是上圖中，綠色框里面剩下的資料，還是待選擇的狀態
//res，就是最后的結果
private void getFullPermute(int[] nums, int i, List<List<Integer>> res) {
    if (i == nums.length) {
        ArrayList<Integer> tmp = new ArrayList<>();
        for (int data : nums) {
            tmp.add(data);
        }
        res.add(tmp);
        return;
    }

    //回圈遍歷剩下的資料
    for (int j = i; j < nums.length; j++) {
        swap(nums, i, j); //在剩下的資料中，選取一個，放到當前i位置，然后去做遞回
        
        getFullPermute(nums, i + 1, res);
        
        //交換之后，也應交換回來，保證后面的遞回程序不亂序
        //比如：26行資料交換之前： 0 ~ i-1 ： 123 ；     i~末尾： 456
        //26行交換之后： 0 ~ i-1 ： 123 ；              i~末尾： 546 
        //然后要將剛才交換的資料，重新交換回來：546 -》 456
        //然后才去交換 4 和 6 這兩個資料；  也就是  有無后效性的問題
        swap(nums, i, j); 
    }
}

private void swap(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

三、有重復值的全排列

LeetCode鏈接

這道題和上一道題，本質上是一樣的，只是這道題可能會出現重復值，我們需要過濾掉這些重復，

解法一：我們還是像上道題一樣，生成所有的全排列資料，然后進行用一個方法，進行過濾到重復的資料，此方法是可以的，就是空間和時間有點浪費了，所以我們這里引出一個概念：分支限界，

分支限界

解法二：意思就是說，當在同一個位置的時候，有兩個同樣的資料，都能夠來到這個位置，此時我們只需執行一個這樣的資料，另外一個同樣的資料，我們就不執行（避免）它；聽著可能有點糊涂，來看圖片吧！

所以，我們只需在第二道題的代碼基礎之上，加一個機制，用于判斷數值曾經來沒來過這個位置，就能篩選出所有的重復的全排列，

public List<List<Integer>> permute(int[] nums) {
    if (nums == null) {
        return null;
    }
    List<List<Integer>> res = new ArrayList<>();
    getFullPermute(nums, 0, res); //遞回呼叫子程序
    return res;
}

//nums， 是所有的資料，
//nums[0 ... i - 1] 范圍內，是已經確定好的資料
//nums[i...] 范圍上的資料，就是上圖中，綠色框里面剩下的資料，還是待選擇的狀態
//res，就是最后的結果
private void getFullPermute(int[] nums, int i, List<List<Integer>> res) {
    if (i == nums.length) {
        ArrayList<Integer> tmp = new ArrayList<>();
        for (int data : nums) {
            tmp.add(data);
        }
        res.add(tmp);
        return;
    }

    HashSet<Integer> visited = new HashSet<>(); //用于存盤數值，來沒來過這個位置
    //回圈遍歷剩下的資料
    for (int j = i; j < nums.length; j++) {
        if(!visited.contains(nums[j])) {
            visited.add(nums[j]); //添加已經來過這個位置的資料
            swap(nums, i, j); //在剩下的資料中，選取一個，放到當前i位置，然后去做遞回
        
            getFullPermute(nums, i + 1, res);

            //交換之后，也應交換回來，保證后面的遞回程序不亂序
            //比如：26行資料交換之前： 0 ~ i-1 ： 123 ；     i~末尾： 456
            //26行交換之后： 0 ~ i-1 ： 123 ；              i~末尾： 546 
            //然后要將剛才交換的資料，重新交換回來：546 -》 456
            //然后才去交換 4 和 6 這兩個資料；  也就是  有無后效性的問題
            swap(nums, i, j);
        } 
    }
}

private void swap(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

好啦，本期更新，就到此結束啦！各位同學，我們下期見！！！