代碼隨想錄 - Day34 - 回溯：遞增子序列+排列問題

491. 遞增子序列

如果有相等的整數(shù)也算遞增序列
遞增子序列中至少有兩個(gè)元素 (遍歷的時(shí)候不用遍歷nums中最后一個(gè)元素)

輸入：nums = [4,6,6,2,8]
輸出：[[4,6],[4,6,6],[4,6,6,8],[4,6,8],[4,8],[6,6],[6,6,8],[6,8],[2,2],[2,2,8],[2,8]]

class Solution:
    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])
            # 注意這里不要加return，因?yàn)橐渖系墓?jié)點(diǎn)

        uset = set()    # 用set()對(duì)本層元素去重
        for i in range(startIndex, len(nums)):
            # 排除重復(fù)的情況，跳過遞減的情況
            if (path and nums[i] < path[-1]) or (nums[i] in uset):
                continue
            uset.add(nums[i])       # 記錄這個(gè)元素在本層用過了，本層后面不能再用了
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)    # 遞歸
            path.pop()  # 回溯

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, 0, [], result)
        return result

題目說了數(shù)值范圍，所以還可以用哈希表去重，速度比set()快很多。
但是，個(gè)人覺得沒必要，因?yàn)榉旁趯?shí)際情況中一般不會(huì)給數(shù)值范圍。

class Solution:
    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])
            # 注意這里不要加return，因?yàn)橐渖系墓?jié)點(diǎn)

        used = [0] * 201  # 使用數(shù)組來進(jìn)行去重操作，題目說數(shù)值范圍[-100, 100]
        for i in range(startIndex, len(nums)):
            # 排除重復(fù)的情況，跳過遞減的情況
            # 這里是利用數(shù)組的下標(biāo)和數(shù)組中存儲(chǔ)的元素來進(jìn)行去重
            if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:
                continue
            used[nums[i] + 100] = 1  # 標(biāo)記當(dāng)前元素已經(jīng)使用過
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)    # 遞歸
            path.pop()  # 回溯

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, 0, [], result)
        return result

46.全排列

全排列，即[1,2]和[2,1]算作兩種排列，所以這道題的result要收集所有的葉子節(jié)點(diǎn)
nums 中的所有整數(shù)互不相同，因此無需考慮去重

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

這種題就要考慮新的問題了，即它每次的startIndex都是固定的，遇到取過的數(shù)時(shí)則需要跳過

class Solution:
    def backtracking(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:     # 遇到取過的數(shù)時(shí)則需要跳過
                continue
            used[i] = True  # 取過的數(shù)設(shè)為True
            path.append(nums[i])
            self.backtracking(nums, used, path, result)
            path.pop()      # 回溯
            used[i] = False # 回溯后把該數(shù)設(shè)回False

    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        self.backtracking(nums, used, [], result)
        return result

考慮跳過用過的數(shù)時(shí)，腦子里第一反應(yīng)是dict，卻忘記了用更為簡單的數(shù)組也可以…

47. 全排列 II

相較于上一題，需要考慮去重的問題，dict貌似有用武之地了

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

class Solution:
    def backtracking(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            # 要去重的是 用過且重復(fù) 的數(shù)
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
                continue
            if used[i] == False:     # 遇到取過的數(shù)時(shí)則需要跳過
                used[i] = True  # 取過的數(shù)設(shè)為True
                path.append(nums[i])
                self.backtracking(nums, used, path, result)
                path.pop()      # 回溯
                used[i] = False # 回溯后把該數(shù)設(shè)回False

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        nums.sort()             # 提前排好序，方便后續(xù)去重
        self.backtracking(nums, used, [], result)
        return result

感覺今天這幾道題思路好想，代碼不好寫，總會(huì)在一些細(xì)節(jié)上出錯(cuò)，需要多練習(xí)。

以及，mermaid畫圖好麻煩。。文章來源地址http://www.zghlxwxcb.cn/news/detail-699014.html

到了這里，關(guān)于代碼隨想錄 - Day34 - 回溯：遞增子序列+排列問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！