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):continuepath.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[:])returnfor i in range(len(nums)):if used[i]:continuepath.append(nums[i])used[i] = 1self.backtracking(nums, used, path, result)# 做回溯used[i] = 0path.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[:])returnfor 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 breakpath.append(nums[i])used[i] = 1self.backtracking(nums, used, path, result)used[i] = 0path.pop()def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()  # 排序result = []self.backtracking(nums, [0]*len(nums), [], result)return result