leetcode「組合」題目匯總 回溯法

2020/4/30

39. 組合總和

題意
  • 在無(wú)重復(fù)數(shù)組candidates中尋找和為target的組合。
  • candidates中的數(shù)字可以無(wú)限制重復(fù)被選取。
栗子
輸入: candidates = [2,3,6,7], target = 7,
所求解集為:
[
  [7],
  [2,2,3]
]
關(guān)鍵點(diǎn)
  • 無(wú)重復(fù)數(shù)組：無(wú)需去重。
  • 元素可以重復(fù)選取：遞歸的時(shí)候i不用加1。

回溯要素

  • 選擇：candidates[k, len(candidates) - 1]中任一元素
  • 終止條件：
    • 情況1：找到這樣的組合，即target == 0
    • 情況2：此路不通，即target < 0
代碼
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        subset = []
        self.backtrack(candidates, 0, subset, res, target)
        return res

    def backtrack(self, candidates, k, subset, res, target):
        if target == 0:
            res.append(subset[:])
            return
        if target < 0:
            return

        for i in range(k, len(candidates)):
            # 如果candidates有重復(fù)元素，需要加一句：
            # if i != k and candidates[i] == candidates[i - 1]:
            # continue
            # 當(dāng)然，前提是candidates有序
            subset.append(candidates[i])
            self.backtrack(candidates, i, subset, res, target - candidates[i])
            # 如果元素不可以重復(fù)選取，需要改成
            # self.backtrack(candidates, i + 1, subset, res, target - candidates[i])
            del subset[-1]

40. 組合總和 II

題意
  • 在數(shù)組candidates中尋找和為target的組合。
  • candidates中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
栗子
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
關(guān)鍵點(diǎn)：剛好和上道題相反
  • 有重復(fù)數(shù)組：需要去重。
  • 元素不能重復(fù)選?。哼f歸的時(shí)候i要加1。

回溯要素

  • 選擇：candidates[k, len(candidates) - 1]中的元素，但該層不能有重復(fù)元素
  • 終止條件：
    • 情況1：找到這樣的組合，即target == 0
    • 情況2：此路不通，即target < 0
代碼
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        subset = []
        # 先排序
        candidates.sort()
        self.backtrack(candidates, 0, subset, res, target)
        return res

    def backtrack(self, candidates, k, subset, res, target):
        if target == 0:
            res.append(subset[:])
            return
        
        if target < 0:
            return
        for i in range(k, len(candidates)):
            # 去重/剪枝
            if i != k and candidates[i] == candidates[i - 1]:
                continue
            subset.append(candidates[i])
            # 因?yàn)閏andidates的每個(gè)數(shù)字只能使用一次，所以i + 1
            self.backtrack(candidates, i + 1, subset, res, target - candidates[i])
            del subset[-1]

216. 組合總和 III

題意
  • 找出所有相加之和為n的k個(gè)數(shù)的組合。
  • 組合中只允許含有 1 - 9 的正整數(shù)
  • 每種組合中不存在重復(fù)的數(shù)字。
栗子
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
關(guān)鍵點(diǎn)
  • 元素不能重復(fù)選取：遞歸的時(shí)候i要加1。

回溯要素

  • 選擇：[m, 9]中的元素
  • 終止條件：
    • 情況1：找到這樣的組合，即k == len(combination)且n == 0
    • 情況2：此路不通，即k == len(combination)且n != 0，或者k != len(combination)且n == 0
代碼
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        combination = []
        res = []
        self.backtrack(k, n, 1, combination, res)
        return res

    def backtrack(self, k, n, m, combination, res):
        if k == len(combination):
            if n == 0:
                res.append(combination[:])
            return
        
        for i in range(m, 10):
            combination.append(i)
            self.backtrack(k, n - i, i + 1, combination, res)
            del combination[-1]

377. 組合總和 Ⅳ

題意
  • 給定一個(gè)不存在重復(fù)數(shù)字的數(shù)組nums，找出和為target的組合的個(gè)數(shù)。
  • 順序不同的序列被視作不同的組合。
栗子
nums = [1, 2, 3]
target = 4

所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

請(qǐng)注意，順序不同的序列被視作不同的組合。

因此輸出為 7。
關(guān)鍵點(diǎn)
  • nums不存在重復(fù)數(shù)字：不用去重
  • 元素不僅可以重復(fù)選取，而且可以不按順序：遍歷i的時(shí)候從0到len(nums)-1
  • 求個(gè)數(shù)，不用返回具體的數(shù)組：return 個(gè)數(shù)，不用傳遞combination和res了。
回溯要素
  • 選擇：nums[0, len(nums)-1]的任一元素
  • 終止條件：
    • 情況1：找到這樣的組合，即target == 0
    • 情況2：此路不通，即target < 0
算法優(yōu)化

使用哈希映射表mp來(lái)存儲(chǔ){target: times}，避免重復(fù)計(jì)算。

代碼
from collections import defaultdict
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        self.res = 0
        mp = defaultdict(int)
        return self.backtrack(nums, target, mp)

    def backtrack(self, nums, target, mp):
        if target in mp:
            return mp[target]
        if target == 0:
            self.res += 1 
            return 1
        if target < 0:
            return 0
        
        res = 0
        for i in range(len(nums)):
            res += self.backtrack(nums, target - nums[i], mp)
        mp[target] = res
        return res
dp方法
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        # dp[0]初始化為1
        dp[0] = 1
        # 循環(huán)順序一定不能亂
        for i in range(1, target + 1):
            for j in range(len(nums)):
                if nums[j] > i:
                    continue
                dp[i] += dp[i - nums[j]]
        return dp[target]

518. 零錢兌換 II

  • 給定一個(gè)不存在重復(fù)數(shù)字的數(shù)組coins，找出和為amount的組合的個(gè)數(shù)。
  • coins可重復(fù)使用。
  • 順序不同的序列視為相同的組合。
栗子
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
tricky之處
  • 如果延續(xù)377. 組合總和 Ⅳ的思路：
    • 上題是求排列，這題是求組合。
    • 既然上題是從在arr[0, len(arr) - 1]的區(qū)間進(jìn)行枚舉，那么這道題在arr[i, len(arr)-1]的區(qū)間不就好了嗎。左邊界從0變?yōu)?code>i，表示會(huì)選擇遞增的元素，把這道題變成組合問(wèn)題；左邊界不是i + 1，因?yàn)橛矌趴梢阅枚啻巍?/li>
  • 看起來(lái)算法是完全正確的。但是呢...
    • 我們這道題不是返回combination，而是返回個(gè)數(shù)，如果不使用hashmap，就會(huì)陷入超時(shí)。而如果使用了hashmap，算法就不正確了。
    • 下面給出一段錯(cuò)誤代碼。注意，這段代碼和377. 組合總和 Ⅳ的結(jié)果一樣，左邊界是i還是0完全失去效力。如果不使用mp進(jìn)行緩存，結(jié)果就正確了。
錯(cuò)誤代碼
from collections import defaultdict

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        mp = defaultdict(int)
        return self.dfs(amount, coins, 0, mp)

    def dfs(self, amount, coins, k, mp):
        if amount in mp:
            return mp[amount]
        if amount == 0:
            return 1
        if amount < 0:
            return 0
        
        res = 0
        # 寫成range(len(coins))是一樣的
        for i in range(k, len(coins)):
            res += self.dfs(amount - coins[i], coins, i, mp)
        
        mp[amount] = res
        return res
解釋
  • 錯(cuò)誤原因
    • 上段代碼的決策樹(shù)如圖左所示。盡管枚舉時(shí)索引是非遞減的，但加入mp后就不是這樣了。
    • 我們看虛線框，這里mp緩存的是{2: 2}，當(dāng)金額為2時(shí)，有兩種硬幣組合方法。那看中間的虛線框處，將[1,2,1,1]也計(jì)算在內(nèi)，就打破了非遞減的特性。

    • 所以，這種思路是不正確的。


      示意圖
正確做法
  • 如圖右的決策樹(shù)所示，共coins.length層。
  • 選擇：coins[k]拿多少個(gè)
  • 終止條件：
    • 情況1：找到這樣的組合，即amount == 0
    • 情況2：此路不通，即amount < 0
  • mp是{(k, amount): times}的映射
正確代碼
from collections import defaultdict

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        mp = defaultdict(int)
        return self.dfs(amount, coins, 0, mp)

    def dfs(self, amount, coins, k, mp):
        if k == len(coins):
            if amount == 0:
                return 1
            return 0
        if amount < 0:
            return 0
        if (k, amount) in mp:
            return mp[(k, amount)]
        
        res = 0
        for i in range(amount // coins[k] + 1): # 注意加1
            res += self.dfs(amount - i * coins[k], coins, k + 1, mp)
        
        mp[(k, amount)] = res
        return res
dp方法
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            for c in coins:
                if i - c < 0:
                    continue # 不能break，因?yàn)橛矌挪灰欢ㄉ?                dp[i] = min(dp[i], dp[i-c] + 1)
        return dp[-1] if dp[-1] != float('inf') else -1

77. 組合

題意
  • 找出1 ... n中所有可能的 k 個(gè)數(shù)的組合。
  • 每種組合中不存在重復(fù)的數(shù)字。
栗子
輸入: n = 4, k = 2
輸出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
關(guān)鍵點(diǎn)
  • 元素不能重復(fù)選取：遞歸的時(shí)候i要加1。
回溯要素
  • 選擇：nums[1, n]中的元素，倒著找
  • 終止條件：
    • 情況1：找到這樣的組合，即k == 0
    • 情況2：此路不通，即n < k
代碼
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        combination = []
        res = []
        self.backtrack(n, k, combination, res)
        return res
        
    def backtrack(self, n, k, combination, res):
        if k == 0:
            res.append(combination[:])
            return
        
        if n < k:
            return 

        for i in range(n, 0, -1):
            combination.append(i)
            self.backtrack(i - 1, k - 1, combination, res)
            del combination[-1]

17. 電話號(hào)碼的字母組合

題意
  • 給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。

  • 給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。


栗子
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
回溯要素
  • 終止條件：遍歷完digits字符串，即k == len(digits)
  • 選擇：該數(shù)字對(duì)應(yīng)的字母
代碼
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        mp = {'2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z']}
        res = []
        self.backtrack(digits, 0, mp, '', res)
        return res

    
    def backtrack(self, digits, k, mp, combination, res):
        if k == len(digits):
            res.append(combination) #string是值傳遞，不是引用傳遞
            return
        for ch in mp[digits[k]]:
            self.backtrack(digits, k + 1, mp, combination + ch, res)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容