Java回溯法解決全排列問題流程詳解

更新時間：2022年10月03日 11:08:00 作者：劉婉晴

從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當(dāng)m=n時所有的排列情況叫全排列。這篇文章主要介紹了Java回溯法解決全排列問題

題目描述：

給定一不重復(fù)的數(shù)組，返回其具有的所有全排列（使用 List<List > 返回）

思路：

以數(shù)組 nums = [1, 2, 3] 為例，其具有的解空間可以用這樣一棵樹表示，相比看到這里大家就可以知道，這是一道可以用回溯法解決的題。

難點：如何保證不選到已經(jīng)使用過的數(shù)組元素 —— 使用 used[] 數(shù)組標(biāo)記該元素是否被使用過

細(xì)節(jié)請看代碼注釋

    // 用于存儲結(jié)果的數(shù)組
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backTrack(nums, list, used);
        return ans;
    }
    // 回溯法參數(shù)： nums為待排列數(shù)組， list存儲當(dāng)前排列結(jié)果， used[]標(biāo)記當(dāng)前元素是否被使用過
    public void backTrack(int[] nums, List<Integer> list, boolean[] used){
        // 回溯法退出條件，list大小為nums[]長度，即所有元素都已加入排列
        if(list.size() == nums.length){
            // 加入結(jié)果數(shù)組，注意要 new 新的list (List為按指針?biāo)傅刂反鎯?，不然每次加的都是同一個)
            ans.add(new ArrayList(list));
            return;
        }
        // 循環(huán)以每個元素開始排列
        for(int i=0; i<nums.length; i++){
            // 元素未被使用過加入排列
            if(!used[i]){
                // 在排列中加入當(dāng)前元素，并將used[i]修改為true
                list.add(nums[i]);
                used[i] = true;
                // 遞歸調(diào)用 backTrack
                backTrack(nums, list, used);
                // 回溯，去掉當(dāng)前元素，并將used置為false
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }

變式一

題目描述：給定一具有重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列

示例：

這道題是全排列的變式題，只需要對全排列寫法加入對重復(fù)情況去除的判斷即可，于是本題的重心轉(zhuǎn)移到了如何判斷是否會產(chǎn)生重復(fù)序列。

我們可以思考什么情況會產(chǎn)生重復(fù)序列，我們先對 nums[] 按從小到大排序，限制每次填入的數(shù)字都是重復(fù)數(shù)字的從左到右的第一個數(shù)字

class Solution {
    Boolean[] visit;
    List<List<Integer>> ans;
    public List<List<Integer>> permuteUnique(int[] nums) {
        visit = new Boolean[nums.length];
        Arrays.fill(visit, false);
        List<Integer> list = new ArrayList<>();
        ans = new ArrayList<>();
        Arrays.sort(nums);
        backTrack(nums, list);
        return ans;
    }
    public void backTrack(int[] nums, List<Integer> list){
        if(nums.length == list.size()){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i=0; i<nums.length; i++){
            // 當(dāng)前元素用過 + 限制每輪填入的字符都是重復(fù)字符的從左到右的第一個字符
            if(visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1])){
                continue;
             }
            list.add(nums[i]);
            visit[i] = true;
            backTrack(nums, list);
            visit[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

變式：字符排序

class Solution {
    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        // 思路： 回溯法典型例題 —— 含重復(fù)問題
        char[] array = s.toCharArray();
        Arrays.sort(array);
        Boolean[] used = new Boolean[array.length];
        Arrays.fill(used, false);
        backTack(array, used, new StringBuilder());
        String[] res = new String[ans.size()];
        for(int i=0; i<ans.size(); i++){
            res[i] = ans.get(i);
        }
        return res;
    }
    public void backTack(char[] array, Boolean[] used, StringBuilder sb){
        if(array.length == sb.length()){
            ans.add(new String(sb));
        }
        for(int i=0; i<array.length; i++){
           if(used[i]){
               continue;
           }
           if(i>0 && array[i]==array[i-1] && !used[i-1]){
               continue;
           }
            sb.append(array[i]);
            used[i] = true;
            backTack(array, used, sb);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}

到此這篇關(guān)于Java回溯法解決全排列問題流程詳解的文章就介紹到這了,更多相關(guān)Java回溯法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: