前言

前面我們通過(guò)幾個(gè)題目基本了解了解決遞歸類問(wèn)題的基本思路和步驟，相信大家對(duì)于遞歸多多少少有了更加深入的了解。那么本篇文章我將為大家分享結(jié)合決策樹(shù)來(lái)解決遞歸、搜索和回溯相關(guān)的問(wèn)題。

什么是決策樹(shù)

決策樹(shù)是一種基本的分類與回歸方法。在分類問(wèn)題中，決策樹(shù)通過(guò)構(gòu)建一棵樹(shù)形圖來(lái)對(duì)數(shù)據(jù)進(jìn)行分類。樹(shù)的每個(gè)節(jié)點(diǎn)表示一個(gè)特征屬性，每個(gè)分支代表一個(gè)特征屬性上的判斷條件，每個(gè)葉節(jié)點(diǎn)代表一個(gè)類別。在回歸問(wèn)題中，決策樹(shù)可以預(yù)測(cè)一個(gè)實(shí)數(shù)值。

下面是一個(gè)簡(jiǎn)單的決策樹(shù)：

知道了什么是決策樹(shù)，下面我們將運(yùn)用決策樹(shù)來(lái)解決實(shí)際問(wèn)題。

1. 全排列

https://leetcode.cn/problems/permutations/

1.1 題目要求

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1]
輸出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整數(shù) 互不相同

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

    }
}

1.2 做題思路

相信大家肯定做過(guò)跟排列相關(guān)的問(wèn)題，就是三個(gè)人坐座位的問(wèn)題。第一座位可以坐A、B、C 任何一個(gè)人，如果第一個(gè)座位坐的是 A 的話，那么第二個(gè)位子 A 就不能再坐了，第二個(gè)位子就只能在 B、C 之間選擇了，如果 B 選擇了第二個(gè)位子，那么第三個(gè)位置就只能 C 選擇了。所以這個(gè)問(wèn)題通過(guò)決策樹(shù)來(lái)體現(xiàn)的話就是這樣的：

但是上面的圖我們會(huì)發(fā)現(xiàn)這幾種情況會(huì)有重復(fù)的情況，那么我們?nèi)绾魏Y選掉這些重復(fù)的情況呢？可以使用一個(gè)標(biāo)記數(shù)組來(lái)記錄已經(jīng)選擇過(guò)的元素，當(dāng)下一次選擇的時(shí)候就選擇這個(gè)標(biāo)記數(shù)組中沒(méi)有被選擇的剩下的元素的其中一個(gè)。這道題目跟上面的例子的思路是一樣的，這里我就不為大家再畫(huà)一個(gè)圖了。

那么這道題使用代碼的思想該如何解決呢？每次遞歸我們還是將數(shù)組中的所有元素都給列舉出來(lái)，不過(guò)我們需要根據(jù)標(biāo)記數(shù)組中元素的使用情況來(lái)選擇是否可以選擇這個(gè)元素，如果某個(gè)元素沒(méi)有被選擇，那么這次就選擇這個(gè)元素，將這個(gè)元素標(biāo)記為已使用，然后繼續(xù)遞歸，當(dāng)當(dāng)前情況列舉完成之后就需要恢復(fù)現(xiàn)場(chǎng)，當(dāng)路徑集合中記錄的元素的個(gè)數(shù)和數(shù)組中的元素個(gè)數(shù)相同的時(shí)候，就說(shuō)明一種情況已經(jīng)列舉完成，就可以將當(dāng)前情況添加進(jìn)ret集合中，返回。

1.3 代碼實(shí)現(xiàn)

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    boolean[] vis;
    public List<List<Integer>> permute(int[] nums) {
        //對(duì)全局變量進(jìn)行初始化
        path = new ArrayList<>();
        ret = new ArrayList<>();
        vis = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
    	//當(dāng)path中元素的大小等于數(shù)組的大小，就說(shuō)明一種情況已經(jīng)列舉完成，這事需要我們將當(dāng)前path中的數(shù)據(jù)添加進(jìn)ret中，并且返回
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
       for (int i = 0; i < nums.length; i++) {
           if (vis[i] == false) {
               path.add(nums[i]);
               //將當(dāng)前元素標(biāo)記為已使用
               vis[i] = true;
               //考慮該位置之后的其他元素的選擇
               dfs(nums);
               //恢復(fù)現(xiàn)場(chǎng)
               path.remove(path.size() - 1);
               vis[i] = false;
           }
       }
    }
}

2. 子集

https://leetcode.cn/problems/subsets/

2.1 題目要求

給你一個(gè)整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）。

解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。

示例 1：

輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

輸入：nums = [0]
輸出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

    }
}

2.2 做題思路

前面全排列中是當(dāng)路徑集合中的元素個(gè)數(shù)和數(shù)組中的元素的個(gè)數(shù)相同的時(shí)候視為一種情況，這道題目就不一樣了，這個(gè)是數(shù)組的子集，也就是說(shuō)每一種情況的元素的個(gè)數(shù)可能是不一樣的，所以我們路徑集合每新添加一個(gè)元素就可以視為一種情況，就需要將路徑中的元素添加進(jìn)ret集合中，思路跟上一道題目是類似的，都是通過(guò)決策樹(shù)遞歸來(lái)實(shí)現(xiàn)的，但是呢？仔細(xì)看題目可以發(fā)現(xiàn)，就是集合[1,2]，[2,1]是一種情況，也就是說(shuō)子集的選擇跟順序無(wú)關(guān)，那么我們又該如何避免出現(xiàn)重復(fù)的情況呢？

這其實(shí)也不難，想想如果是在數(shù)學(xué)中我們會(huì)怎樣思考？如果當(dāng)前位置我們選擇了某個(gè)元素，那么后面的位置我們就從這個(gè)元素的后面元素中去選擇。

所以通過(guò)代碼體現(xiàn)的話，就是我們可以使用一個(gè) pos 變量來(lái)記錄當(dāng)前位置選擇的元素的下標(biāo)，然后下一個(gè)位置選擇元素遞歸的話，我們就從 pos 的下一個(gè)位置開(kāi)始選擇。

2.3 代碼實(shí)現(xiàn)

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> subsets(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(nums, 0)
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        //進(jìn)入這個(gè)函數(shù)就可以將path中的結(jié)果添加進(jìn)ret中，這樣就可以將空集的情況給考慮上
        ret.add(new ArrayList<>(path));
        //循環(huán)的話，就從pos位置開(kāi)始遍歷
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

3. 找出所有子集的異或總和再求和

https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

3.1 題目要求

一個(gè)數(shù)組的 異或總和 定義為數(shù)組中所有元素按位 XOR 的結(jié)果；如果數(shù)組為 空 ，則異或總和為 0 。

例如，數(shù)組 [2,5,6] 的 異或總和 為 2 XOR 5 XOR 6 = 1 。
給你一個(gè)數(shù)組 nums ，請(qǐng)你求出 nums 中每個(gè) 子集 的 異或總和 ，計(jì)算并返回這些值相加之 和 。

注意：在本題中，元素 相同 的不同子集應(yīng) 多次 計(jì)數(shù)。

數(shù)組 a 是數(shù)組 b 的一個(gè) 子集 的前提條件是：從 b 刪除幾個(gè)（也可能不刪除）元素能夠得到 a 。

示例 1：

輸入：nums = [1,3]
輸出：6
解釋：[1,3] 共有 4 個(gè)子集：
- 空子集的異或總和是 0 。
- [1] 的異或總和為 1 。
- [3] 的異或總和為 3 。
- [1,3] 的異或總和為 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

輸入：nums = [5,1,6]
輸出：28
解釋：[5,1,6] 共有 8 個(gè)子集：
- 空子集的異或總和是 0 。
- [5] 的異或總和為 5 。
- [1] 的異或總和為 1 。
- [6] 的異或總和為 6 。
- [5,1] 的異或總和為 5 XOR 1 = 4 。
- [5,6] 的異或總和為 5 XOR 6 = 3 。
- [1,6] 的異或總和為 1 XOR 6 = 7 。
- [5,1,6] 的異或總和為 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

輸入：nums = [3,4,5,6,7,8]
輸出：480
解釋：每個(gè)子集的全部異或總和值之和為 480 。

提示：

1 <= nums.length <= 12
1 <= nums[i] <= 20

class Solution {
    public int subsetXORSum(int[] nums) {

    }
}

3.2 做題思路

這道題目跟上面的子集思路基本上沒(méi)什么區(qū)別，之不過(guò)上面的子集是要求出所有子集的情況，而這道題目是求出所有子集異或之后的總和。因?yàn)樗悸坊靖蟼€(gè)題一樣，所以我們直接來(lái)看代碼。

3.3 代碼實(shí)現(xiàn)

class Solution {
    int path;
    int ret;
    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return ret;
    }

    private void dfs(int[] nums, int pos) {
        //前面是將集合添加進(jìn)ret中，這里我們是將每種情況加進(jìn)ret中
        ret += path;
        for (int i = pos; i < nums.length; i++) {
            //這里我們不是將新加入的元素加入到path集合中，而是將新加入的元素和之前path元素的異或的結(jié)果異或
            path ^= nums[i];
            dfs(nums, i + 1);
            //恢復(fù)現(xiàn)場(chǎng)（兩個(gè)相同的元素異或，結(jié)果為0）
            path ^= nums[i];
        }
    }
}

4. 全排列II

https://leetcode.cn/problems/permutations-ii/

4.1 題目要求

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 1：

輸入：nums = [1,1,2]
輸出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {

    }
}

4.2 做題思路

這道題目跟 全排列I 是不一樣的，全排列I 中不存在重復(fù)的元素，但是這道題目中存在重復(fù)的元素，也就是說(shuō)[1, 1, 2] 和 [1, 1, 2] 是同一個(gè)排列，這不看起來(lái)就是同一個(gè)排列嗎？難道還能不同嗎？其實(shí)這里的 1 不是同一個(gè)1，[1(下標(biāo)為0), 1(下標(biāo)為1), 2]，[1(下標(biāo)為1), 1(下標(biāo)為0), 2]，全排列I 中我們只需要使用一個(gè)標(biāo)記數(shù)組來(lái)避免同一個(gè)元素被重復(fù)使用的情況，而這個(gè) 全排列II 中，我們還需要篩選出因元素相同而導(dǎo)致的相同排列的情況。那么如何篩選呢？我們來(lái)看個(gè)例子：

4.3 代碼實(shí)現(xiàn)

class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        vis = new boolean[nums.length];
        //首先將重復(fù)元素給排序到一起
        Arrays.sort(nums);
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (vis[i] == false && (i == 0 || (nums[i - 1] != nums[i]) || vis[i - 1] == true)) {
                path.add(nums[i]);
                vis[i] = true;
                dfs(nums);
                //恢復(fù)現(xiàn)場(chǎng)
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-760837.html

到了這里，關(guān)于【算法系列篇】遞歸、搜索和回溯（四）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！