题解 | #牛棚分组#
牛棚分组
https://www.nowcoder.com/practice/d5740e4dde3740828491236c53737af4
知识点:回溯
思路:使用 List<List<Integer>> 来存储组合的结果。我们使用递归函数实现深度优先搜索,在搜索的过程中构建组合。我们记录当前已选数字的个数和当前数字的起始值,并在递归的过程中分别选择当前数字或不选择当前数字
编程语言:java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @param k int整型 * @return int整型二维数组 */ public int[][] combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); dfs(res, new ArrayList<>(), 1, k, n); return toArray(res); } private void dfs(List<List<Integer>> res, List<Integer> path, int x, int u, int n) { if (u == 0 || x > n) { if (x <= n + 1 && u == 0) { res.add(new ArrayList<>(path)); } return; } path.add(x); dfs(res, path, x + 1, u - 1, n); path.remove(path.size() - 1); dfs(res, path, x + 1, u, n); } private int[][] toArray(List<List<Integer>> res) { int[][] arr = new int[res.size()][]; for (int i = 0; i < res.size(); i++) { List<Integer> list = res.get(i); arr[i] = new int[list.size()]; for (int j = 0; j < list.size(); j++) { arr[i][j] = list.get(j); } } return arr; } }