数据结构与算法：回溯（下）：子集相关力扣题（78.子集、90.子集Ⅱ、491.非递减子序列）、排列相关力扣题（46.全排列、47.全排列Ⅱ）

1.子集相关力扣题

78.子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
    	# 注意一开始要放入空子集
        ans = [[]]
        def backtracking(cur:int, path:List[int]) -> None:
            if len(path) == len(nums):
                return
            for i in range(cur, len(nums)):
                path.append(nums[i])
                # 区别只是在每处理一个节点的时候，就需要放入结果集
                ans.append(path.copy())
                backtracking(i+1, path)
                path.pop()
            return
        backtracking(0,[])
        return ans

效率：0ms，击败100.00%

90.子集Ⅱ

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        nums.sort()
        def backtracking(cur:int, path:List[int]) -> None:
            if len(path) == len(nums):
                return
            for i in range(cur,len(nums)):
                if i>cur and nums[i]==nums[i-1]:
                    # 跳过重复元素
                    continue
                path.append(nums[i])
                ans.append(path.copy())
                backtracking(i+1, path)
                path.pop()
            return
        backtracking(0,[])
        return ans

效率：0ms，击败100.00%

491.非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

1 <= nums.length <= 15
-100 <= nums[i] <= 100

初版代码

一开始我的代码如下：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<2:
            return []
        ans = []
        def backtracking(cur:int, path:List[int]) -> None:
        	"""
        	因为还是在一个集合中挑选数。
        	所以需要用cur来记录该集合中已经遍历到哪了，防止重复
        	"""
            if cur==len(nums):
                return
            for i in range(cur, len(nums)):
			"""
	 		因为数组中可能含有重复元素，而答案要求去重。
	 		所以数组遍历时，遇到相同的数就跳过。
	 		但注意，因为答案要求的子序列是不能改变其在数组的先后顺序的。
	 		所以在这我们不应在开始给数组排序。
			"""	 		
                if i>cur and nums[i]==nums[i-1]:
                    continue
                if path and nums[i]<path[-1]:
                # 判断是否是非递减
                    continue
                path.append(nums[i])
                ans.append(path.copy())
                backtracking(i+1,path)
                path.pop()
            return
        backtracking(0, [])
        # 最后过滤长度小于2的元素
        filtered_ans = [path for path in ans if len(path)  >=2]
        return filtered_ans

这个代码通过了47 / 58。当遇到序列：[1,2,1,1] 时，其输出是：

[[1,2],[1,1],[1,1,1],[1,1]]

但实际上正确输出应该是

[[1,2],[1,1],[1,1,1]]

这很明显是去重出了问题。那对于这种abaa式的例子，为什么去重出了错误？
因为答案允许的是

a1 b
a1 a2
a1 a2 a3

但代码生成的是

a1 b
a1 a2
a1 a2 a3
a2 a3

其中，a1 a2和a2 a3会被认定为重复。如果数组排序了，那么a1、a2、a3会因为相邻在一起，从而被

if i>cur and nums[i]==nums[i-1]:
      continue

去重。

但是因为数组没有排序，所以此时的去重只针对原本在数组中就相邻的重复元素，譬如a2和a3，但因为a1与他们不相邻，所以没办法去掉。

所以，我们应该考虑换一种去重方式，关注到题目说-100 <= nums[i] <= 100，这实际上是个很小的范围，那么我们就可以使用专门的集合来记录已使用的数字。

其次，我们要考虑的是这个集合应该定义在那，因为``

最后就是关于长度小于2的元素应该被过滤，实际上可以放在终止条件那，只有当path的长度≥2时，我们才收集结果。

终版代码

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        if len(nums)<2:
            return []
        ans = []
        def backtracking(cur:int, path:List[int]) -> None:
            if len(path) >= 2:
                ans.append(path.copy())
            used = set() # 对每一层进行去重，而不是整体去重，否则收集不到如题目示例1中的[7,7]的答案
            for i in range(cur, len(nums)):
                if path and nums[i]<path[-1]:
                    continue
                if nums[i] in used:
                    continue
                used.add(nums[i])
                path.append(nums[i])
                backtracking(i+1,path)
                path.pop()
            return
        backtracking(0, [])
        return ans

效率：19ms，击败86.55%

这里还有一个非常小的优化点，就是我们要关注两个剪枝的顺序。

如果你把if nums[i] in used放在前面，其实效率差不多是20ms, 击败50%左右的程度。

这是因为if path and nums[i]<path[-1]分别是内置长度的判断，和直接索引判断两个数，是O(1)的复杂度。能筛选nums[i]是不是一个值得继续遍历的值。

如果是值得遍历的值，再去看它是否已经用过。所以将它放在前面效率会更快一点。

2.排列相关力扣题

46.全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtracking(path:List[int], used:set) -> None:
            if len(path) == len(nums):
                ans.append(path.copy())
                return
            for i in range(len(nums)):
                if nums[i] in used:
                    continue
                path.append(nums[i])
                used.add(nums[i])
                backtracking(path, used)
                path.pop()
                used.remove(nums[i])
            return
        backtracking([], set())
        return ans

效率：3ms，击败46.01%

47.全排列Ⅱ

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()  # 对数组进行排序，方便去重
        used = [False] * len(nums)  # 用于记录元素是否被使用过
        
        def backtracking(path: List[int]) -> None:
            if len(path) == len(nums):
                ans.append(list(path))
                return
            
            for i in range(len(nums)):
                # 跳过重复元素
                if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
                    continue
                
                used[i] = True
                path.append(nums[i])
                backtracking(path)
                path.pop()
                used[i] = False
        
        backtracking([])
        return ans

效率：11ms，击败27.40%