数据结构与算法 / 系统课时
排列、组合与子集
排列、组合与子集
排列、组合和子集都能用回溯生成,但它们对顺序、选择数量和候选范围的要求不同。本课用同一组输入实现三种生成器,通过一个主示例直接比较 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 的组合有 个。输出规模本身已经是指数级或阶乘级,因此算法不可能在生成全部结果时达到多项式总时间。
保存答案时必须复制路径。若直接保存同一个可变列表引用,后续回溯会修改已经记录的结果。
按自己的节奏,确认真正理解。