代码随想录刷题第二十九天| 491.递增子序列 * 46.全排列 * 47.全排列 II

代码随想录刷题第二十九天

递增子序列 (LC 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, startindex):
        if len(self.path)>1:
            self.result.append(self.path[:])

        uset = []   
        for i in range(startindex, len(nums)):
            if nums[i] in uset or (self.path and nums[i] < self.path[-1]):
                continue
            else:
                uset.append(nums[i])
                self.path.append(nums[i])
                self.backtracking(nums, i+1)
                self.path.pop()

全排列 (LC 46)

题目思路：

代码实现：

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

    def permute(self, nums: List[int]) -> List[List[int]]:
        used = [0 for _ in range(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[:])
            return

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

全排列II (LC 47)

题目思路：

代码实现：

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

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        used = [0 for _ in range(len(nums))]
        nums.sort()
        self.backtracking(nums, used)
        return self.result        
        
    def backtracking(self, nums, used):
        if len(self.path) == len(nums):
            self.result.append(self.path[:])
            return

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