leetcode刷题-回溯算法04

491.递增子序列

leetcode题目链接
代码随想录文档讲解

思路：

与上一题不同，不能用used列表，因为这个题不能排序，
在每一个for循环里面用一个集合记录遍历过的数

伪代码（C++）：

python代码：

class Solution:
    def backtracking(self, nums, start_index, path, result):
        if len(path) > 1:
            result.append(path[:])
        used = set()
        for i in range(start_index, len(nums)):
            if (path and nums[i] < path[-1]) or (nums[i] in used):
                continue
            path.append(nums[i])
            used.add(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.全排列

leetcode题目链接
代码随想录文档讲解

思路：

排列（考虑顺序）和组合问题（不考虑顺序）的区别
借助used数组（需要进入递归）

python代码：

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]:
                continue
            path.append(nums[i])
            used[i] = 1
            self.backtracking(nums, used, path, result)
            # 做回溯
            used[i] = 0
            path.pop()
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        self.backtracking(nums, used, [], result)
        return result

47.全排列II

leetcode题目链接
代码随想录文档讲解

思路：

集合中有重复元素，去重，（排序）（数层去重used[i-1]==False）

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] == 1) or (i >0 and nums[i] == nums[i-1] and used[i-1] == 0):
                continue # not break
            path.append(nums[i])
            used[i] = 1
            self.backtracking(nums, used, path, result)
            used[i] = 0
            path.pop()
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 排序
        result = []
        self.backtracking(nums, [0]*len(nums), [], result)
        return result