排列-组合-子集算法总结

概念

组合、排列、子集是 leetcode 中比较常见的题目系列,主要区别在于:

名称 概念 示例题目
排列 每项结果有序,即[1,2] 与 [2,1]是两个结果 46. 全排列47. 全排列 II
组合 每项结果无序,即[1,2]与[2,1]是一个结果 39. 组合总和216. 组合总和 III40. 组合总和 II77. 组合
子集 与组合类似,但会有额外的限制,比如数量等 78. 子集90. 子集 II

排列与组合

抽取类题目

元素没有重复也不能复选

nums 中的元素都是唯一的,每个元素最多可以使用一次。

  • 排列伪代码

即题目 46. 全排列 的解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def back_track(self, nums, track_list, used_pos):
if len(track_list) == len(nums):
self.res.append(track_list.copy())

for idx in range(len(nums)):
if used_pos[idx]:
continue

# 做选择
track_list.append(nums[idx])
used_pos[idx] = True

self.back_track(nums, track_list, used_pos)

# 撤销选择
track_list.pop(-1)
used_pos[idx] = False
  • 组合伪代码

77. 组合 的解

1
2
3
4
5
6
7
8
def back_track(self, n, start, k):
if len(self.track_list) == k:
self.res.append(self.track_list.copy())
for idx in range(start, n + 1):
# 做选择
self.track_list.append(idx)
self.back_track(n, idx + 1, k)
self.track_list.pop(-1)

元素重复但不能复选

  • 排列伪代码

47. 全排列 II 的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def back_track(self, nums, track_list, used_pos):
if len(track_list) == len(nums):
self.res.append(track_list.copy())

for idx in range(len(nums)):
if used_pos[idx]:
continue
if idx > 0 and nums[idx] == nums[idx - 1] and not used_pos[idx - 1]:
"""
若当前元素与上一个元素相同,那么从当前元素开始的回溯,应该要跳过。
如何判断从**当前元素开始的回溯**:从当前元素开始,代表这上一个元素还未回溯到(未使用到),可以直接跳过。
"""
continue
# 进行选择
track_list.append(nums[idx])
used_pos[idx] = True

self.back_track(nums, track_list, used_pos)
# 取消选择
del track_list[-1]
used_pos[idx] = False
  • 组合伪代码

90. 子集 II 的解

1
2
3
4
5
6
7
8
9
10
11
def back_track(self, nums, start):
self.res.append(self.track_list.copy())
for idx in range(start, len(nums)):
if idx != start and nums[idx] == nums[idx - 1]:
continue
# 做选择
self.track_list.append(nums[idx])
self.back_track(nums, idx + 1)

# 撤销选择
self.track_list.pop(-1)

元素无重复可以复选

  • 排列伪代码

删除了去重逻辑,并且也不需要再考虑 used_pos

1
2
3
4
5
6
7
8
9
def back_track(self, nums, track_list):
for idx in range(len(nums)):
# 进行选择
track_list.append(nums[idx])

self.back_track(nums, track_list, used_pos)
# 取消选择
del track_list[-1]

  • 组合伪代码
1
2
3
4
5
6
7
def back_track(self, nums):
for idx in range(len(nums)):
# 做选择
self.track_list.append(nums[idx])
self.back_track(nums)
# 撤销选择
self.track_list.pop(-1)

求和类问题

和已知(target 已知)

典型题目 39. 组合总和40. 组合总和 II

39 题为组合类题目,但可以复选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
self.track_list = []
self.track_sum = 0

candidates = sorted(candidates)
self.back_track(candidates, 0, target)
return self.res

def back_track(self, candidates, start, target):
if self.track_sum == target:
self.res.append(self.track_list.copy())

for idx in range(start, len(candidates)):
if self.track_sum + candidates[idx] > target:
# 后边的更大,不用考虑了
continue

self.track_sum += candidates[idx]
self.track_list.append(candidates[idx])

self.back_track(candidates, idx, target)

self.track_list.pop(-1)
self.track_sum -= candidates[idx]

40 题目为组合类问题,但不能复选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def __init__(self):
self.res = []
self.track_list = []
self.track_sum = 0

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 一些边界条件
if sum(candidates) < target:
return self.res

candidates = sorted(candidates)
self.back_track(candidates, 0, target)
return self.res

def back_track(self, candidates, start, target):
if self.track_sum > target:
return
if self.track_sum == target and self.track_list not in self.res:
self.res.append(self.track_list.copy())
return

for idx in range(start, len(candidates)):
if idx > start and candidates[idx] == candidates[idx - 1]:
# 避免重复数导致耗时增加
continue
self.track_sum += candidates[idx]
self.track_list.append(candidates[idx])

self.back_track(candidates, idx + 1, target)

self.track_list.pop(-1)
self.track_sum -= candidates[idx]

组数量已知(k已知)

典型题目 698. 划分为k个相等的子集

我实现的第一个代码是

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 canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
target_num = sum(nums) / k
return self.back_track(nums, 0, [[] for _ in range(k)], target_num)

def back_track(self, nums, index, bucket, target_num):
if index == len(nums):
for sub_list in bucket:
if target_num != sum(sub_list):
return False
return True

for i in range(len(bucket)):
# 做选择
bucket[i].append(nums[index])
if self.back_track(nums, index + 1, bucket, target_num):
return True

# 撤销选择
bucket[i].pop(-1)

return False

这个实现是从数字的角度出发,判断每个数字是否应该进入某个桶,比较明显的超时了。

从桶的角度出发,如果当前的桶已经满足了要求,那么就只需要 k - 1 需要进一步的考虑。另外,bucket 与 track_sum 的设计,也是与之前的角度是相反的。并且同时使用到了 used_pos 和 start 的设计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
def __init__(self):
self.state_res_cache = {}

def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
if k > len(nums):
return False

target_num = sum(nums) // k
if sum(nums) != target_num * k:
return False

nums = sorted(nums, reverse=True)
return self.back_track(k, nums, 0, 0, [False] * len(nums), target_num)

def back_track(self, k, nums, start, bucket, used_pos, target_num):
"""
:param k: 桶的数量
:param nums: 原始数组
:param start: 数组中开始的位置
:param bucket: 当前桶的大小
:param used_pos: 使用过的位置
:param target_num: 目标数量
:return:
"""
if k == 0:
# 所有的桶都被装满了
return True

state = tuple(used_pos)

if bucket == target_num:
# 在当前使用位置状态的
res = self.back_track(k=k - 1, nums=nums, start=0, bucket=0, used_pos=used_pos, target_num=target_num)
self.state_res_cache[state] = res
return res

if state in self.state_res_cache:
# 因为会走重复的路
return self.state_res_cache[state]

for idx in range(start, len(nums)):
if used_pos[idx]:
# 已使用
continue
if nums[idx] + bucket > target_num:
# 已装满
continue
bucket += nums[idx]
used_pos[idx] = True
if self.back_track(k, nums, idx + 1, bucket, used_pos, target_num):
return True
bucket -= nums[idx]
used_pos[idx] = False

return False

排列-组合-子集算法总结

https://iii.run/archives/329e5487d798.html

作者

mmmwhy

发布于

2022-11-13

更新于

2023-01-11

许可协议

评论