90. Subsets II

今天挑選了「90. Subsets II」的題目，這是一道類似「排列組合」的練習題。排列組合的基本想法就是把所有的可能窮舉出來，重點在於如何讓這個過程窮舉的過程更有效率。所以在本題裡面我們試著用遞迴的概念來轉化原本的問題，試著讓過程可以被簡化。

先看一下題目描述

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

再搭配範例理解題目

• Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

• Example 2:

Input: nums = [0]
Output: [[],[0]]

Subsets（子集合）是從原始資料中任意挑選部分的元素所形成的集合稱之，這個題目要把所有的 Subsets 挑選出來。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：窮舉法

第一種方法採用窮舉法的方法用兩個迴圈把所有可能都跑過一次，只是在過程中會將「已經被考慮過元素組合剔除」。

用 Python 實作一次

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	
        nums.sort()
        ans = [[]]
        
        for num in nums:
            for index in range(len(ans)):
                temp = ans[index] + [num]
                if temp not in ans:
                    ans.append(temp)
        
        return ans

也可以用 JavaScript 復刻一次

var subsetsWithDup = function(nums) {
    nums.sort((a,b)=>a-b);
    
    let ans = [[]]
    for (let num of nums){
        let l = ans.length;
        for (let j = 0; j < l; j++) {
            tmp = [...ans[j], num]
            if(!ans.includes(tmp))
                ans.push(tmp);
        }
    }
    return [...new Set(ans.map(JSON.stringify))].map(JSON.parse);
};

提得一提的是由於 JavaScript 會有 deep copy 的問題，所以這邊用了一個比較 tricky 的方法來處理 not in 的判斷。

方法 ②：遞迴法

「任意挑選部分的元素」這個行為很像是排列組合（permutation）在做的事情，所以這裡我們使用遞迴的方式來處理 permutation 議題，從一個元素開始，每一層多增加一個元素的方式直到全部考慮完畢。大致的概念如下圖：

用 Python 實作一次

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        powerset = []
        
        def permute(arr, index):
            powerset.append(arr)
            for i in range(index, len(nums)):
                if i != index and nums[i] == nums[i-1]:
                    continue
                permute(arr+[nums[i]], i+1)

                         
        permute([], 0)
        return powerset

也可以用 JavaScript 復刻一次

var subsetsWithDup = function(nums) {
    nums.sort()
    const powerset = [];
    
    function permute(arr, index) {
        powerset.push(arr)     
        for(let i = index; i < nums.length; i++) {
            if(i !== index && nums[i] === nums[i-1])
                continue;
            permute([...arr, nums[i]], i+1)
        }
    }
    permute([], 0);
    return powerset;
};

反思沉澱

在這個題目中，我們試圖將原始的排列問題轉化成遞迴的概念來解。透過遞迴來記憶部分的資訊，再每一層展開時只需要計算那些真的需要被計算的部分，而不用真的窮舉出所有的可能。這個搭配遞迴來簡化窮舉法的方法稱為「回溯（Backtracking）」，核心概念就是在窮舉的過程中盡可能的篩選掉不符合的組合。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 78. Subsets
• 1982. Find Array Given Subset Sums

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。