组合算法(Java实现)

Manan
Page content

组合算法

排列组合是一个重要的数学概念，组合通常用来枚举从一个集合中选择特定个数元素的所有结果。

实现与思路阐述

实现方式：递归 + 回溯法。

时间复杂度: O(n ^ x)，其中x代表选择元素的个数。

递归回溯

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

public final class CombinationAlgorithm<ElementType> {

    private final List<List<ElementType>> res = new ArrayList<>();

    private void doSelect(List<ElementType> collection, int start, int selectionNumber, List<ElementType> container) {
        if (selectionNumber == 0) {
            res.add(new ArrayList<>(container));
            return;
        }

        for (int i = start, len = collection.size(); i < len; ++i) {
            container.add(collection.get(i));
            doSelect(collection, i + 1, selectionNumber - 1, container);
            // 回溯
            container.remove(container.size() - 1);
        }
    }

    public List<List<ElementType>> select(List<ElementType> collection, int selectionNumber) {
        if (selectionNumber > collection.size())
            throw new IllegalArgumentException("selectionNumber can't greater than collection's length");
        res.clear();
        doSelect(collection, 0, selectionNumber, new ArrayList<>());
        return res;
    }

}

select函数参数解释

  1. collection 数据集合

  2. selectionNumber 选择的数目

doSelect函数参数解释

  1. collection 数据集合

  2. start 数据集合开始的位置

  3. selectionNumber 选择的数目

  4. container 临时存放每次选择的结果

标准递归回溯代码模板

if (condition) {
    // 收集结果
    // 返回
}
for (xxxxxxx) {
    // 加入元素
    // 递归调用
    // 进行回溯
}