29天【代码随想录算法训练营34期】第七章 回溯算法part05 (491.递增子序列 * 46.全排列 * 47.全排列 II)

491.递增子序列
如果在最前面加一个uset = set（），这个就是给这一层一个used set，很好用，不错

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, [], result, 0)
        return result
    def backtracking(self, nums, path, result, index):
        if len(path) > 1:
            result.append(path[:])
        uset = set()
        for i in range(index, len(nums)):
            if (path and nums[i] < path[-1]) or nums[i] in uset:
                continue
            else:
                path.append(nums[i])
                uset.add(nums[i])
                self.backtracking(nums, path, result, i+1)
                path.pop()

46.全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, result, [], [False] * len(nums))
        return result
    
    def backtracking(self, nums, result, path, used):
        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] = True
            self.backtracking(nums, result, path, used)
            path.pop()
            used[i] = False

47.全排列 II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        self.backtracking(nums, result, [], [False]*len(nums))
        return result
    def backtracking(self, nums, result, path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if i>0 and used[i-1] and nums[i] == nums[i-1]:
                continue
            if used[i] == True:
                continue
            path.append(nums[i])
            used[i] = True
            self.backtracking(nums, result, path, used)
            path.pop()
            used[i] = False