集合为N的排列组合 - litonghui/TechBlog GitHub Wiki

利用回溯方法解决排列组合问题是比较有效的方法之一，需要注意的是避免同一元素被多次使用，例如：

1. 实现一个算法，两个参数 n 和 k，返回所有k 在1到n中的所有组合，其中 1 <= k <= n，例如 n=4，k=2，则返回 { [2,4],[3,4],[2,3],[1,2],[1,3],[1,4] }

2. 实现一个算法，给定一个数组，返回所有可能的排列组合。例如[1,2,3]，则返回 { [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] }

分析算法一：回归数学题，简单理解即为在n中选择k个数，C(n.k)可以算出总共有多少种可能，通过计算机语言去求解所有的可能性，可以利用回溯算法去求解所有可能性，需要注意是每个小集合的size 不能超过2，当我们选择第一个元素1，第二个元素选择2，满足条件，将[1,2]存储起来，当然第二个元素可以为3...,因此我们需要将元素最新加入的元素2去除，增加元素3,以此类推到n；当1 作为第一个元素所有组合都查找完成，需要将元素2作为第一个元素，查找后面的所有可能。[2,3(4,5,6...)],依次类推到n-k 作为第一个元素结束。

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> out = new ArrayList<>();
    levelCombine(res, out, n, k, 1);
    return res;
}

/**
 * 建立一个保存最终结果的大集合res，定义一个保存每一个组合的小集合out，
 * 每次放一个数到out里，如果out里数个数到了k个，则把out保存到最终结果中，否则在下一层中继续调用递归。
 * @param res
 * @param n
 * @param k out 集合的 size
 * @param start 当前元素
 */
public void levelCombine(List<List<Integer>> res,List<Integer> out, int n, int k,int start) {
    if (out.size() == k) {
        res.add(new ArrayList<>(out));
        return;
    }
    for (int i = start; i <= n; i++) {
        out.add(i);
        levelCombine(res, out, n, k, i + 1);
        out.remove(out.size() - 1);
    }
}

分析算法二：回归数学问题，其实质为所有元素的排列组合:n!，其中 n 为数组的长度。同理借助回溯方法求解，将数组中所有的元素从第一个开始加入集合out，避免重复添加，比如添加元素1，回溯查找除1以外的其他元素，添加out 中，如果out size 等于 数组长度，add res 并返回；添加成功过的元素需要删除，保证其他元素可以添加。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    if(nums.length!=0) {
        List<Integer> out = new ArrayList<>();
        levelPermute(res, out, nums);
    }
    return res;
}

public void levelPermute(List<List<Integer>> res,List<Integer> out, int[] nums) {
    if (out.size() == nums.length) {
        res.add(new ArrayList<>(out));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!out.contains(nums[i])) {
            out.add(nums[i]);
            levelPermute(res, out, nums);
            out.remove(out.size() - 1);
        }
    }
}
Add a custom footer
⚠️ **GitHub.com Fallback** ⚠️