Leetcode刷题记录——回溯子集篇
Leetcode78 子集
子集和组合的思想类似，但是子集是在路径搜索过程中，都要记录当前的路径加入res中
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def __init__(self):
self.res = []
self.path = []
def subsets(self, nums: List[int]) -> List[List[int]]:
self.res.append([])
self.backtracking(nums, 0)
return self.res
def backtracking(self, nums, startIndex):
if startIndex == len(nums):
return
for i in range(startIndex, len(nums)):
self.path.append(nums[i])
self.res.append(self.path[:])
self.backtracking(nums, i+1)
self.path.pop()
|
Leetcode90 子集Ⅱ
与上题类似，但是本题nums会出现重复元素
这个重复元素在递归时是可以重复出现的，但是在for循环时，如果前面的元素与当前相同，那就会出现收集重复子集的情况
这题与之前的去重逻辑一样，用一个used数组记录是否访问元素
在递归时，若nums[i] == nums[i-1] and used[i-1] == 1是不要紧的，因为是往后继续收集
但在for循环时，若i > 0 and nums[i] == nums[i-1] and used[i-1] == 0，表明上个相同的元素用过了，但不在递归中，因此要跳过
但nums首先需要排序
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def __init__(self):
self.res = []
self.path = []
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
used = [0] * len(nums)
nums.sort()
self.res.append([])
self.backtracking(nums, 0, used)
return self.res
def backtracking(self, nums, startIndex, used):
if startIndex == len(nums):
return
for i in range(startIndex, len(nums)):
if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:
continue
else:
self.path.append(nums[i])
used[i] = 1
self.res.append(self.path[:])
self.backtracking(nums, i+1, used)
self.path.pop()
used[i] = 0
|
Leetcode491 非递减子序列
因为要保证子序列，所以不能事先对nums排序了
按要求收集所有path，最后去重
还有一个树层去重思路留到下次更新，想不动了
Python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def __init__(self):
self.res = set()
self.path = []
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
self.backtracking(nums, 0)
return list(self.res)
def backtracking(self, nums, startIndex):
if startIndex == len(nums):
return
for i in range(startIndex, len(nums)):
if len(self.path) > 0:
if i > 0 and nums[i] < self.path[-1]:
continue
self.path.append(nums[i])
if len(self.path) >= 2:
self.res.add(tuple(self.path[:]))
self.backtracking(nums, i+1)
self.path.pop()
|