用Java编写一个实验程序,采用回溯法输出自然数1~ n 中任取 r 个数的所有组合。
时间: 2024-02-09 09:13:23 浏览: 91
从n个数组中取出所有排列组合(Java实现)
5星 · 资源好评率100%
好的,以下是回溯法输出自然数1~n中任取r个数的所有组合的Java代码:
```java
import java.util.ArrayList;
import java.util.List;
public class CombinationGenerator {
public static void main(String[] args) {
int n = 5; // 自然数1~n
int r = 3; // 任取r个数
List<List<Integer>> combinations = generateCombinations(n, r);
System.out.println("自然数1~" + n + "中任取" + r + "个数的所有组合:");
for (List<Integer> combination : combinations) {
System.out.println(combination);
}
}
private static List<List<Integer>> generateCombinations(int n, int r) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> currentCombination = new ArrayList<>();
backtrack(combinations, currentCombination, 1, n, r);
return combinations;
}
private static void backtrack(List<List<Integer>> combinations, List<Integer> currentCombination, int start, int n, int r) {
if (currentCombination.size() == r) {
combinations.add(new ArrayList<>(currentCombination));
return;
}
for (int i = start; i <= n; i++) {
currentCombination.add(i);
backtrack(combinations, currentCombination, i + 1, n, r);
currentCombination.remove(currentCombination.size() - 1);
}
}
}
```
代码中的 `generateCombinations` 方法接受两个参数:`n` 表示自然数1~n,`r` 表示任取r个数。它返回一个 `List<List<Integer>>` 对象,其中每个 `List<Integer>` 对象表示一种组合。代码中使用了回溯法来生成所有组合。具体来说,我们从1开始遍历到n,将每个数都加入当前组合中,然后递归地向后遍历,直到组合的长度达到r。如果当前组合的长度等于r,则将它加入结果集中,然后回溯到上一个状态,继续遍历下一个数。
阅读全文