求子集的多種方式｜Java

題目描述

這是 LeetCode 上的 ​​90. 子集 II​​ ，難度為 中等。

Tag : 「位運算」、「回溯算法」、「狀态壓縮」、「DFS」

給你一個整數數組 nums ，其中可能包含重複元素，請你傳回該數組所有可能的子集（幂集）。

解集 不能 包含重複的子集。傳回的解集中，子集可以按 任意順序 排列。

示例 1：

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

輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]      

示例 2：

輸入：nums = [0]

輸出：[[],[0]]      

提示：

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

回溯解法（Set）

由于是求所有的方案，而且資料範圍隻有 10，可以直接用爆搜來做。

同時由于答案中不能包含相同的方案，是以我們可以先對原數組進行排序，進而確定所有爆搜出來的方案，都具有單調性，然後配合 Set 進行去重。

代碼：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return new ArrayList<>(ans);
    }

    /**
     * @param nums 原輸入數組
     * @param u 目前決策到原輸入數組中的哪一位
     * @param cur 目前方案
     * @param ans 最終結果集
     */
    void dfs(int[] nums, int u, List<Integer> cur, Set<List<Integer>> ans) {
        // 所有位置都決策完成，将目前方案放入結果集
        if (nums.length == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 選擇目前位置的元素，往下決策
        cur.add(nums[u]);
        dfs(nums, u + 1, cur, ans);

        // 不選目前位置的元素（回溯），往下決策
        cur.remove(cur.size() - 1);
        dfs(nums, u + 1, cur, ans);
    }
}      

• 時間複雜度：排序複雜度為，爆搜複雜度為，每個方案通過深拷貝存入答案，複雜度為。整體複雜度為
• 空間複雜度：總共有個方案，每個方案最多占用空間，整體複雜度為

回溯解法

我們知道使用 Set 雖然是 操作，但是隻是均攤 。

是以我們來考慮不使用 Set 的做法。

我們使用 Set 的目的是為了去重，那什麼時候會導緻的重複呢？

其實就是相同的元素，不同的決策方案對應同樣的結果。

舉個????，[1,1,1] 的資料，隻選擇第一個和隻選擇第三個（不同的決策方案），結果是一樣的。

是以如果我們希望去重的話，不能單純的利用「某個下标是否被選擇」來進行決策，而是要找到某個數值的連續一段，根據該數值的選擇次數類進行決策。

還是那個????，[1,1,1] 的資料，我們可以需要找到數值為 1 的連續一段，然後決策選擇 0 次、選擇 1 次、選擇 2 次 ... 進而確定不會出現重複

也就是說，将決策方案從「某個下标是否被選擇」修改為「相同的數值被選擇的個數」。這樣肯定不會出現重複，因為 [1,1,1] 不會因為隻選擇第一個和隻選擇第三個産生兩個 [1] 的方案，隻會因為 1 被選擇一次，産生一個 [1] 的方案。

代碼：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return ans;
    }

    /**
     * @param nums 原輸入數組
     * @param u 目前決策到原輸入數組中的哪一位
     * @param cur 目前方案
     * @param ans 最終結果集
     */
    void dfs(int[] nums, int u, List<Integer> cur, List<List<Integer>> ans) {
        // 所有位置都決策完成，将目前方案放入結果集
        int n = nums.length;
        if (n == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 記錄目前位置是什麼數值（令數值為 t），并找出數值為 t 的連續一段
        int t = nums[u];
        int last = u;
        while (last < n && nums[last] == nums[u]) last++;

        // 不選目前位置的元素，直接跳到 last 往下決策
        dfs(nums, last, cur, ans);

        // 決策選擇不同個數的 t 的情況：選擇 1 個、2 個、3 個 ... k 個
        for (int i = u; i < last; i++) {
            cur.add(nums[i]);
            dfs(nums, last, cur, ans);
        }

        // 回溯對數值 t 的選擇
        for (int i = u; i < last; i++) {
            cur.remove(cur.size() - 1);
        }
    }
}      

• 時間複雜度：排序複雜度為，爆搜複雜度為，每個方案通過深拷貝存入答案，複雜度為。整體複雜度為
• 空間複雜度：總共有個方案，每個方案最多占用空間，整體複雜度為

狀态壓縮解法（Set）

由于長度隻有 10，我們可以使用一個 int 的後 10 位來代表每位數組成員是否被選擇。

同樣，我們也需要先對原數組進行排序，再配合 Set 來進行去重。

代碼：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();

        // 枚舉 i 代表，枚舉所有的選擇方案狀态
        // 例如 [1,2]，我們有 []、[1]、[2]、[1,2] 幾種方案，分别對應了 00、10、01、11 幾種狀态
        for (int i = 0; i < (1 << n); i++) {
            cur.clear();
            // 對目前狀态進行諸位檢查，如果目前狀态為 1 代表被選擇，加入目前方案中
            for (int j = 0; j < n; j++) {
                int t = (i >> j) & 1;
                if (t == 1) cur.add(nums[j]);
            }
            // 将目前方案中加入結果集
            ans.add(new ArrayList<>(cur));
        }
        return new ArrayList<>(ans);
    }
}      

• 時間複雜度：排序複雜度為，爆搜複雜度為，每個方案通過深拷貝存入答案，複雜度為。整體複雜度為
• 空間複雜度：總共有個方案，每個方案最多占用空間，整體複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.90​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先将所有不帶鎖的題目刷完。