数据结构与算法 / 系统课时

排列、组合与子集

排列、组合与子集

排列、组合和子集都能用回溯生成,但它们对顺序、选择数量和候选范围的要求不同。本课用同一组输入实现三种生成器,通过一个主示例直接比较 used 与 start 两类状态设计。

学习目标

  • 区分排列、组合和子集的结果语义
  • 为不同枚举问题选择 used 或 start 状态
  • 正确确定记录答案的时机

三类问题的核心差异

给定互不相同的元素 1、2、3,排列中 [1,2,3] 与 [2,1,3] 不同;组合中 [1,2] 与 [2,1] 代表同一选择;子集不限制选择数量,空集也是合法结果。

类型 顺序是否重要 候选范围 记录答案时机
排列 是 每层扫描全部未使用元素 路径长度等于 n
组合 否 从 start 向后选择 路径长度等于 k
子集 否 从 start 向后选择 每个递归节点

排列组合子集的决策树对比

主示例:统一比较三种生成方式

下面的 Java 17 程序对输入 {1, 2, 3} 生成全排列、长度为 2 的组合和全部子集。输入假设互不相同;若含重复值,还需要排序与同层去重。

java
import java.util.ArrayList;
import java.util.List;

public class EnumerationDemo {

    public static void main(String[] args) {
        int[] values = {1, 2, 3};

        System.out.println("permutations = " + permutations(values));
        System.out.println("combinations = " + combinations(values, 2));
        System.out.println("subsets = " + subsets(values));
    }

    private static List<List<Integer>> permutations(int[] values) {
        List<List<Integer>> result = new ArrayList<>();
        buildPermutations(
            values,
            new boolean[values.length],
            new ArrayList<>(),
            result
        );
        return result;
    }

    private static void buildPermutations(
        int[] values,
        boolean[] used,
        List<Integer> path,
        List<List<Integer>> result
    ) {
        if (path.size() == values.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < values.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(values[i]);
            buildPermutations(values, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    private static List<List<Integer>> combinations(
        int[] values,
        int count
    ) {
        List<List<Integer>> result = new ArrayList<>();
        if (count < 0 || count > values.length) {
            return result;
        }
        buildCombinations(
            values, count, 0, new ArrayList<>(), result
        );
        return result;
    }

    private static void buildCombinations(
        int[] values,
        int count,
        int start,
        List<Integer> path,
        List<List<Integer>> result
    ) {
        if (path.size() == count) {
            result.add(new ArrayList<>(path));
            return;
        }

        int need = count - path.size();
        // 剩余元素不足时不再进入无效分支。
        for (int i = start; i <= values.length - need; i++) {
            path.add(values[i]);
            buildCombinations(
                values, count, i + 1, path, result
            );
            path.remove(path.size() - 1);
        }
    }

    private static List<List<Integer>> subsets(int[] values) {
        List<List<Integer>> result = new ArrayList<>();
        buildSubsets(values, 0, new ArrayList<>(), result);
        return result;
    }

    private static void buildSubsets(
        int[] values,
        int start,
        List<Integer> path,
        List<List<Integer>> result
    ) {
        // 子集树中的每个节点都对应一个答案。
        result.add(new ArrayList<>(path));

        for (int i = start; i < values.length; i++) {
            path.add(values[i]);
            buildSubsets(values, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

预期输出:

text
permutations = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
combinations = [[1, 2], [1, 3], [2, 3]]
subsets = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

为什么状态不能混用

排列每层都要重新扫描全部元素,因此需要 used[i] 表示某个下标是否已出现在当前路径;若误用 start,只会生成下标递增的少量结果。

组合和子集不关心顺序,使用 start 让后续下标严格递增,从源头避免 [1,2] 与 [2,1] 这类顺序重复。组合只在路径达到指定长度时记录,子集则进入每个状态时都记录。

结果规模与边界

n 个互不相同元素的全排列有 n! 个,全部子集有 2^n 个,长度为 k 的组合有 C(n,k)C(n,k) 个。输出规模本身已经是指数级或阶乘级,因此算法不可能在生成全部结果时达到多项式总时间。

保存答案时必须复制路径。若直接保存同一个可变列表引用,后续回溯会修改已经记录的结果。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

排列、组合与子集

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通