python求数组的所有子集_python求子集

求n个数的全排列

全排列-定义： 从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

题目： 我们假设要求三个数的全排列，我们可以写一个3级的for循环,，最后可得到三个数全排列方式的数目：

def combination_three():
    count = 0
    for i in range(1,4):
        for j in range(1,4):
            for k in range(1,4):
                if i !=j and j!=k and i!=k:
                    print(i, j, k)
                    count += 1
    return count
1
2
3
4
5
6
7
8
9

运行结果：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
6
1
2
3
4
5
6
7
8

题目： 假设要求10个数的全排列，就需要写10级的for循环。假设要求n个数的全排列，应该怎么写呢？
以下是使用递归实现求n个数全排列：

def permute(nums: list):
    def backtrack(first = 0):
        # 所有数都填完了
        if first == n:
            res.append(nums[:])
            return
        for i in range(first, n):
            # 动态维护数组
            nums[first], nums[i] = nums[i], nums[first]
            # 继续递归填下一个数
            backtrack(first + 1)
            # 撤销操作
            nums[first], nums[i] = nums[i], nums[first]

    n = len(nums)
    res = []
    backtrack()
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

以下是使用循环求n个数全排列：

def permute2(nums: list[int]):
    n = len(nums)
    stack = [(0, [])]  # 初始状态：索引为0，空列表

    result = []

    while stack:
        index, curr_perm = stack.pop()

        if index == n:
            result.append(curr_perm)
        else:
            for num in nums:
                if num not in curr_perm:
                    stack.append((index + 1, curr_perm + [num]))

    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Next subject

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

def find_subsets(nums):
    def backtrack(start, path):
        subsets.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    subsets = []
    backtrack(0, [])
    return subsets

# 示例
nums = [1,1,3]
result = find_subsets(nums)
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

拓展：

1. 使用递归完成
2. 使用循环完成

参考文章：

1. 回溯算法求解
2. 求解组合子集和排列
3. C++版递归实现全排列讲解视频
4. 求全排列