m个数 生成n个数的所有组合 详解

要从给定的 m 个数 中生成 n 个数的所有组合，我们可以使用递归或迭代方法，具体解决过程如下：

1. 问题说明

给定一个大小为 m 的数组，例如 [1, 2, 3]，生成所有长度为 n 的组合（可以包括重复数字，也可以不包括）。

两种组合方式：

1. 组合（不允许重复）：

   • 每个数字只能使用一次。
   • 如果 n > m，则没有解。
   • 示例：从 [1, 2, 3] 中选出长度为 2 的组合，结果为：[1, 2], [1, 3], [2, 3]。

2. 带重复的组合（允许重复）：

   • 每个数字可以被重复使用。
   • 示例：从 [1, 2, 3] 中选出长度为 2 的组合，结果为：[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]。

2. 实现方案

2.1 不允许重复的组合

算法思路

• 使用递归来构造结果。
• 每次选择一个数字后，不能再选择它（避免重复）。
• 当选够了 n 个数字 时，将结果加入最终答案。

实现代码

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

public class Combinations {
    public static List<List<Integer>> generateCombinations(int[] nums, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, n, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int n, int start, List<Integer> current, List<List<Integer>> result) {
        // 如果组合长度达到目标 n，添加到结果中
        if (current.size() == n) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 从 start 开始，依次选择数字
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]); // 选择当前数字
            backtrack(nums, n, i + 1, current, result); // 递归选择剩余的数字
            current.remove(current.size() - 1); // 回溯
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int n = 2;
        List<List<Integer>> combinations = generateCombinations(nums, n);
        System.out.println(combinations); // 输出: [[1, 2], [1, 3], [2, 3]]
    }
}

运行流程

• 假设输入数组为 [1, 2, 3]，目标组合长度为 2：
  1. 从 1 开始，递归选择 2 和 3，生成 [1, 2] 和 [1, 3]。
  2. 从 2 开始，递归选择 3，生成 [2, 3]。
  3. 最终结果为：[[1, 2], [1, 3], [2, 3]]。

2.2 允许重复的组合

算法思路

• 使用递归来构造结果。
• 每次选择一个数字后，仍然可以选择它（允许重复）。
• 当选够了 n 个数字 时，将结果加入最终答案。

实现代码

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

public class CombinationsWithRepetition {
    public static List<List<Integer>> generateCombinations(int[] nums, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, n, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int n, int start, List<Integer> current, List<List<Integer>> result) {
        // 如果组合长度达到目标 n，添加到结果中
        if (current.size() == n) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 从 start 开始，依次选择数字（可以重复选择）
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]); // 选择当前数字
            backtrack(nums, n, i, current, result); // 递归选择剩余的数字（允许重复）
            current.remove(current.size() - 1); // 回溯
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int n = 2;
        List<List<Integer>> combinations = generateCombinations(nums, n);
        System.out.println(combinations); // 输出: [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
    }
}

运行流程

• 假设输入数组为 [1, 2, 3]，目标组合长度为 2：
  1. 从 1 开始，递归选择 1, 2, 3，生成 [1, 1], [1, 2], [1, 3]。
  2. 从 2 开始，递归选择 2, 3，生成 [2, 2], [2, 3]。
  3. 从 3 开始，递归选择 3，生成 [3, 3]。
  4. 最终结果为：[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]。

3. 时间复杂度分析

1. 不允许重复的组合：

   • 假设数组大小为 m，组合长度为 n。
   • 时间复杂度为 $O(C(m,n))=O(\frac{m!}{n!(m-n)!})$，因为每种组合只会生成一次。

2. 允许重复的组合：

   • 时间复杂度为 $O(m^n)$，因为每个位置可以选择 m 种数字，共有 n 个位置。

4. 示例测试

4.1 不允许重复的组合

• 输入：nums = [1, 2, 3], n = 2
• 输出：[[1, 2], [1, 3], [2, 3]]

4.2 允许重复的组合

• 输入：nums = [1, 2, 3], n = 2
• 输出：[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

5. 总结

动态规划或递归回溯是生成组合的常见方法，根据问题需求选择适合的实现方式。