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

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(nums, 0, path, result)
        return result
    
    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])

        uset = set()
        for i in range(startIndex, len(nums)):
            if (path and nums[i] < path[-1]) or nums[i] in uset:
                continue

            uset.add(nums[i])
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)
            path.pop()

# ---------- 递增子序列 ----------
# 1. 每个节点：len(path) > 1 才收集
# 2. 剪枝：
#    - 非递增：nums[i] < path[-1]
#    - 同层重复：nums[i] in uset
# 3. uset 只作用于“同一层递归”

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtracking(nums, [], [False] * len(nums), result)
        return result

    def backtracking(self, nums, path, used, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, path, used, result)
            path.pop()
            used[i] = False
# ---------- 全排列（回溯） ----------
# 1. 每个排列长度 = len(nums)
# 2. used 数组防止重复使用
# 3. for i in range(len(nums))
# 4. 排列 vs 组合：
#    组合：startIndex
#    排列：从头遍历