首页 > 算法阅读：1746

子集问题（非常详细，附带源码）

简单理解，集合指的就是一组元素，比如 {1,2,3,4} 是一个包含 4 个元素的集合。集合中的元素是没有顺序的，比如 {1, 2} 和 {2, 1} 是同一个集合。

子集是数学里的概念，用于描述两个集合之间包含与被包含的关系。假设有两个集合 A 和 B，A 是{1, 2}，B 是{1, 2, 3, 4}，集合 B 包含集合 A 中所有的元素，集合 A 就叫做集合 B 的子集。

子集问题指的是找出给定集合的所有子集。比如 {1, 2, 3} 是一个集合，它的所有子集包括：

{ }、{1}、{2}、{3}、{1, 2}、{1, 3}、{2, 3}、{1, 2, 3}

{ }是空集合，它可以是任何集合的子集。经过统计，集合 {1,2,3} 的子集一共有 8 种。

严格意义上，数学中的集合是不允许包含重复元素的。但有些编程题目允许集合里包含重复元素，本节带大家解决子集问题，也会涉及到包含重复元素的集合。比如集合 {1, 1, 2}，它的所有子集包括：

{ }、{1}、{2}、{1, 1}、{1, 2}，{1, 1, 2}

编程解决子集问题，可以用回溯算法实现，接下来给大家讲解具体的实现思路。

无重复元素集合的子集问题

首先通过一个实例，带大家了解回溯算法解决子集问题的整个过程。

回溯算法查找 {1, 2, 3} 所有子集的过程是：

从空的集合 { } 开始，找到子集 { }；
    将元素 1 添加到集合里，找到子集 {1}；
        将元素 2 添加到集合里，找到子集 {1,2}；
            将元素 3 添加到集合里，找到子集 {1,2,3}；
                没有元素可以选择，回溯到 {1,2} 的状态；
            没有元素可以选择，回溯到 {1} 的状态；
        将元素 3 添加到集合里，找到子集 {1,3}；
            没有元素可以选择，回溯到 {1} 的状态；
        没有元素可以选择，回溯到 { } 空集合的状态；
    将元素 2 添加到集合，找到子集 {2}；
        将元素 3 添加到集合里，找到子集 {2,3}；
            没有元素可以选择，回溯到 {2} 状态；
        没有元素可以选择，回溯到 { } 空集合的状态；
    将元素 3 添加到集合，找到子集 {3}；
        没有元素可以选择，回溯到 { } 空集合的状态；
    没有可以选择的元素，算法执行结束。

整个过程中，为了确保找到的子集是不重复的，每选择一个元素 e，紧接着下次只能选择 e 后面的元素。比如将元素 2 添加到空集合之后，下次只能选择 2 后面的元素 3，而不能选择元素 1，因为 {2, 1} 和前面找到的子集 {1, 2} 是重复的。

下面是回溯算法查找 {1, 2, 3} 所有子集的 C 语言程序：

#include <stdio.h>
#include <stdlib.h>

// 打印一个子集
void printSubset(int subset[], int size) {
    printf("{ ");
    for (int i = 0; i < size; i++) {
        printf("%d ", subset[i]);
    }
    printf("}\n");
}

// 回溯函数，找到所有子集
void subsetBacktrack(int arr[], int subset[], int size, int startIndex, int subsetIndex) {
    // 打印当前的子集
    printSubset(subset, subsetIndex);

    // 遍历剩余的元素
    for (int i = startIndex; i < size; i++) {
        // 将当前元素添加到子集中
        subset[subsetIndex++] = arr[i];
        // 递归调用，用于生成包含当前元素的所有子集
        subsetBacktrack(arr, subset, size, i + 1, subsetIndex);
        // 回溯：移除最近添加的元素，以便于下一个迭代
        subsetIndex--;
    }
}

// 为执行subsetBacktrack()函数做前期准备和扫尾工作
void findAllSubsets(int arr[], int n) {
    // 动态分配数组以存储临时子集
    int* subset = (int*)malloc(n * sizeof(int));
    // 开始回溯过程
    subsetBacktrack(arr, subset, n, 0, 0);
    // 释放分配的内存
    free(subset);
}

int main() {
    int arr[] = { 1, 2, 3 }; // 初始集合
    int n = sizeof(arr) / sizeof(arr[0]); // 计算集合的大小
    // 调用函数，打印所有子集
    findAllSubsets(arr, n);
    return 0;
}

程序中自定义了 3 个函数，真正实现回溯算法的是 subsetBacktrack() 函数，它有 5 个参数，各自的含义是：

arr[]：存储集合的数组；
subset[]：存储子集的数组，定义在 findAllSubsets() 函数里；
size：arr[] 和 subset[] 数组的长度；
startIndex：每次调用函数，可选元素的范围是不断变化的，比如刚开始的可选范围是整个集合 {1, 2, 3}，而选择完元素 1 之后，可选范围变成了 {2, 3}。为了表示可选范围，特意用 startIndex 参数表示可选范围的起始位置。
subsetIndex：记录 subset[] 数组中已经选择好的元素数量。

subsetBacktrack() 函数的执行过程，和前面讲回溯算法查找 {1, 2, 3} 所有子集的过程完全一致，这里不再赘述。程序的执行结果为：

{ }
{ 1 }
{ 1 2 }
{ 1 2 3 }
{ 1 3 }
{ 2 }
{ 2 3 }
{ 3 }

注意，此程序只适用于无重复元素的集合。如果将 main() 函数里的 arr[] 数组改成：

int arr[] = { 1, 1, 2 };

再次执行程序，结果为：

{ }
{ 1 }
{ 1 1 }
{ 1 1 2 }
{ 1 2 }
{ 1 }
{ 1 2 }
{ 2 }

原本{1, 1, 2}的子集有 6 种，输出结果中也全部包含了，只是个别子集重复输出了多次。也就是说，对于存在相同元素的集合，程序中缺少查重的机制。

有重复元素集合的子集

对于有重复元素的集合，前面的程序也能找到所有的子集，只不过缺少查重的机制，导致有些子集找到了多次。接下来尝试修改前面的程序，让它也适用于有重复元素的集合。

修改程序之前，首先要搞清楚重复找到子集的原因。把集合 {1, 2, 3} 替换成 {1, 1, 2}，观察程序的执行过程：

从空的集合 { } 开始，找到子集 { }；
    将元素 1 添加到集合里，找到子集 {1}；
        将元素 1 添加到集合里，找到子集 {1,1}；
            将元素 2 添加到集合里，找到子集 {1,1,2}；
                没有元素可以选择，回溯到 {1,1} 的状态；
            没有元素可以选择，回溯到 {1} 的状态；
        将元素 2 添加到集合里，找到子集 {1,2}；
            没有元素可以选择，回溯到 {1} 的状态；
        没有元素可以选择，回溯到 { } 空集合的状态；
    将元素 1 添加到集合，找到子集 {1}；
        将元素 2 添加到集合里，找到子集 {1,2}；
            没有元素可以选择，回溯到 {1} 状态；
        没有元素可以选择，回溯到 { } 空集合的状态；
    将元素 2 添加到集合，找到子集 {2}；
        没有元素可以选择，回溯到 { } 空集合的状态；
    没有可以选择的元素，算法执行结束。

注意看字体加粗部分，子集 {1} 和 {1, 2} 又重复找了一遍。因为集合中有两个相同的元素 1，先后从它们出发查找子集：

从第一个元素 1 出发查找子集：可以选择的元素范围是 {1,1,2}；
从第二个元素 1 出发查找子集：可以选择的元素范围是 {1,2}。

观察两种情况下的可选元素范围，前者完全包含后者，所以第二种情况找到的所有子集都是重复的。也就是说，从第一个元素 1 出发找完子集之后，就没必要再重新从第二个元素 1 开始查找了。在上面的执行过程中，跳过（过滤掉）字体加粗的部分，程序的执行过程就正确了。

对于包含相同元素的集合，分享一种去重的方法：先把集合中的元素排好序（升序或者降序），然后从第一个元素开始查找子集，对于尚未被选中的元素，如果它和前一个元素相等，并且前一个元素处于未选中状态，就跳过这次查找过程。

下面是按照此方法在 {1, 1, 2} 中查找子集的过程：

对 {1, 1, 2} 进行升序排序；
从空的集合 { } 开始，找到子集 { }；
    从 {1,1,2} 中选择第一个元素 1 添加到集合里，找到子集 {1}；
        从 {1,2} 中选择第二个元素 1，由于前一个元素 1 处于选中状态，因此可以添加到集合里，找到子集 {1,1}；
            从 {2} 中选择元素 2 添加到集合里，找到子集 {1,1,2}；
                没有元素可以选择，回溯到 {1,1} 的状态；
            没有元素可以选择，回溯到 {1} 的状态；
        从 {1,2} 中选择元素 2 添加到集合里，找到子集 {1,2}；
            没有元素可以选择，回溯到 {1} 的状态；
        没有元素可以选择，回溯到 { } 空集合的状态；
    从 {1,1,2} 中选择第二个元素 1，由于前一个元素 1 处于未选中状态，因此直接回溯，跳过这次查找；
    从 {1,1,2} 中选择第三个元素 2，找到子集 {2}；
        没有元素可以选择，回溯到 { } 空集合的状态；
    没有可以选择的元素，算法执行结束。

可以看到，成功跳过了之前字体加粗的部分。注意，之所以要判断前一个相同元素是否处于选中状态，是为了区分以下两种情况：

从 {1, 1, 2} 中选择第一个元素 1 添加到空集合 { } 后，紧接着选择第二个元素 1，从而找到子集 {1,1}，这种情况是不能跳过的，此时前一个元素 1 处于选中状态；
从 {1, 1, 2} 中选择第二个元素 1 添加到空集合 { } 时，找到的子集会和选择第一个元素 1 时重复，这种情况是应该跳过的，此时前一个元素 1 处于未选中状态。

下面是修改后的 C 语言程序，它既能满足在无重复元素的集合中查找所有的子集，也能满足在有重复元素的集合中查找所有的子集：

#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;

//快排cmp函数
int cmp(const void* a, const void* b) {
    return *((int*)a) - *((int*)b);
}

// 打印一个子集
void printSubset(int subset[], int size) {
    printf("{ ");
    for (int i = 0; i < size; i++) {
        printf("%d ", subset[i]);
    }
    printf("}\n");
}

// 回溯函数，找到所有子集
void subsetBacktrack(int arr[], int subset[], bool used[], int size, int startIndex, int subsetIndex) {
    // 打印当前的子集
    printSubset(subset, subsetIndex);

    // 遍历剩余的元素
    for (int i = startIndex; i < size; i++) {
        // 判断当前元素是否和前一个元素相同，如果相同，并且前一个元素是未选中状态，则直接跳过本次循环
        if (i > 0 && (arr[i] == arr[i - 1] && used[i - 1] == false)) {
            continue;
        }
        // 将当前元素添加到子集中
        subset[subsetIndex++] = arr[i];
        // 标记当前元素已经被选中
        used[i] = true;
        // 递归调用，用于生成包含当前元素的所有子集
        subsetBacktrack(arr, subset, used, size, i + 1, subsetIndex);
        // 回溯：移除最近添加的元素，同时修改它的选中状态，以便于下一次迭代
        used[i] = false;
        subsetIndex--;
    }
}

// 为执行subsetBacktrack()函数做前期准备和扫尾工作
void findAllSubsets(int arr[], int n) {
    // 动态分配数组以存储临时子集
    int* subset = (int*)malloc(n * sizeof(int));
    // 动态分配数组以存储各个元素的选中状态
    bool* used = (int*)malloc(n * sizeof(bool));

    //对集合进行排序
    qsort(arr, n, sizeof(int), cmp);

    // 开始回溯过程
    subsetBacktrack(arr, subset, used, n, 0, 0);
    // 释放分配的内存
    free(subset);
    free(used);
}

int main() {
    int arr[] = { 1, 2, 1 }; // 初始集合
    int n = sizeof(arr) / sizeof(arr[0]); // 计算集合的大小

    // 调用函数，打印所有子集
    findAllSubsets(arr, n);

    return 0;
}

和先前的程序相比，主要的改动有三处，分别是：

回溯之前，先对集合进行了排序；
subsetBacktrack() 函数添加了一个名为 used[] 的数组，用来实时记录每个元素的选中状态，值为 false 表示尚未选择，值为 true 表示被选中；
subsetBacktrack() 函数内部的 for 循环里添加了 if 判断语句，如果当前元素与前一个元素相同，且前一个元素处于未选中状态，就直接跳过本次循环，开始下一次循环。

下面是解决子集问题的 Java 程序：

import java.util.Arrays;

public class SubsetFinder {

    // 打印一个子集
    private void printSubset(int[] subset, int size) {
        System.out.print("{ ");
        for (int i = 0; i < size; i++) {
            System.out.print(subset[i] + " ");
        }
        System.out.println("}");
    }

    // 回溯函数，找到所有子集
    private void subsetBacktrack(int[] arr, int[] subset, boolean[] used, int size, int startIndex, int subsetIndex) {
        // 打印当前的子集
        printSubset(subset, subsetIndex);

        // 遍历剩余的元素
        for (int i = startIndex; i < size; i++) {
            // 判断当前元素是否和前一个元素相同，如果相同，并且前一个元素是未选中状态，则直接跳过本次循环
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) {
                continue;
            }
            // 将当前元素添加到子集中
            subset[subsetIndex] = arr[i];
            // 标记当前元素已经被选中
            used[i] = true;
            // 递归调用，用于生成包含当前元素的所有子集
            subsetBacktrack(arr, subset, used, size, i + 1, subsetIndex + 1);
            // 回溯：移除最近添加的元素，同时修改它的选中状态，以便于下一次迭代
            used[i] = false;
        }
    }

    // 为执行subsetBacktrack()函数做前期准备和扫尾工作
    public void findAllSubsets(int[] arr) {
        int n = arr.length;
        int[] subset = new int[n];
        boolean[] used = new boolean[n];
        Arrays.sort(arr); // 对集合进行排序
        subsetBacktrack(arr, subset, used, n, 0, 0);
    }

    public static void main(String[] args) {
        SubsetFinder finder = new SubsetFinder();
        int[] arr = { 1, 2, 1 }; // 初始集合
        finder.findAllSubsets(arr); // 调用函数，打印所有子集
    }
}

下面是解决子集问题的 Python 程序：

# 打印一个子集
def print_subset(subset, size):
    print("{", " ".join(str(subset[i]) for i in range(size)), "}")

# 回溯函数，用于找到所有子集
def subset_backtrack(arr, subset, used, size, start_index, subset_index):
    # 打印当前的子集
    print_subset(subset, subset_index)

    # 遍历剩余的元素
    for i in range(start_index, size):
        # 如果当前元素与前一个元素相同，并且前一个元素未被使用，则跳过
        if i > 0 and arr[i] == arr[i - 1] and not used[i - 1]:
            continue
       
        # 将当前元素添加到子集中
        subset[subset_index] = arr[i]
        subset_index += 1
        used[i] = True  # 标记当前元素已被使用
       
        # 递归调用，继续添加下一个元素
        subset_backtrack(arr, subset, used, size, i + 1, subset_index)
       
        # 回溯，移除最近添加的元素，并取消元素的使用标记
        used[i] = False
        subset_index -= 1

# 函数用于初始化并开始回溯过程
def find_all_subsets(arr):
    n = len(arr)
    subset = [0] * n  # 初始化子集数组
    used = [False] * n  # 初始化元素使用标记数组
    arr.sort()  # 对数组进行排序
    subset_backtrack(arr, subset, used, n, 0, 0)

if __name__ == "__main__":
    arr = [1, 2, 1]  # 初始集合
    find_all_subsets(arr)  # 调用函数，打印所有子集

以上程序的执行结果均为：

{ }
{ 1 }
{ 1 1 }
{ 1 1 2 }
{ 1 2 }
{ 2 }

子集问题（非常详细，附带源码）

无重复元素集合的子集问题

有重复元素集合的子集

相关文章