题解 | #牛棚分组#

知识点

递归，dfs

解题思路

使用递归，选择一头牛作为当前组的第一头牛，然后从剩下的牛中选择 k-1 头牛来组成剩余的组。递归结束的条件是 k=0 或者 n<k，表示已经选择完了 k 头牛，或者剩下的牛不够选择了。

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>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        dfs(result, combination, 1, n, k);
        return convertListToArray(result);
    }

    private void dfs(List<List<Integer>> result, List<Integer> combination,
                     int start, int n, int k) {
        if (k == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i <= n - k + 1; i++) {
            combination.add(i);
            dfs(result, combination, i + 1, n, k - 1);
            combination.remove(combination.size() - 1);
        }
    }

    private int[][] convertListToArray(List<List<Integer>> result) {
        int[][] array = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<Integer> list = result.get(i);
            int[] arr = new int[list.size()];
            for (int j = 0; j < list.size(); j++) {
                arr[j] = list.get(j);
            }
            array[i] = arr;
        }
        return array;
    }
}