发表更新代码能力 / 总结10 分钟读完 (大约1531个字)

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

概念

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

名称 概念 示例题目
排列 每项结果有序，即[1,2] 与 [2,1]是两个结果 46. 全排列、47. 全排列 II、
组合 每项结果无序，即[1,2]与[2,1]是一个结果 39. 组合总和、216. 组合总和 III、40. 组合总和 II、77. 组合
子集 与组合类似，但会有额外的限制，比如数量等 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

许可协议

评论

目录

分类

×