头像设计logo_网页建设类有哪些软件_新手20种引流推广方法_上海好的网络推广公司

要从给定的 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. 总结

特性	不允许重复的组合	允许重复的组合
是否允许重复选取	否	是
时间复杂度	$O(C(m,n))$	$O(m^n)$
适用场景	选择独特的对象，避免重复	允许重复选择的对象，例如排列、带放回的抽取。

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