回溯算法491|46|47

491非递减子序列

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

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

    def backTracking(self, nums, start_index) -> List:
        if len(self.path) >= 2:
            self.result.append(self.path[:])
        used = set()
        for i in range(start_index, len(nums)):
            if nums[i] not in used:
                if len(self.path) == 0 or nums[i] >= self.path[-1]:
                    self.path.append(nums[i])
                    used.add(nums[i])
                    self.backTracking(nums, i + 1)
                    self.path.pop()
            else:
                continue
            

46全排列

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        used = [0] * len(nums)
        self.backTracking(nums, used)
        return self.result

    def backTracking(self, nums, used):
        if len(self.path) == len(nums):
            self.result.append(self.path[:])
        for i in range(len(nums)):
            if used[i] == 1:
                continue
            
            self.path.append(nums[i])
            used[i] = 1
            self.backTracking(nums, used)
            self.path.pop()
            used[i] = 0

47全排列II

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        used = [0] * len(nums)
        self.backTracking(nums, used)
        return self.result

    def backTracking(self, nums, used) -> List:
        if len(self.path) == len(nums):
            self.result.append(self.path[:])

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:
                continue
            if used[i] == 0:
                self.path.append(nums[i])
                used[i] = 1
                self.backTracking(nums, used)
                self.path.pop()
                used[i] = 0