题解 | #牛棚分组#

题目考察的知识点:回溯

题目解答方法的文字分析:

核心思想是使用回溯算法，在生成符合要求的牛的组合方案时，每次都选择添加当前牛或不添加当前牛，并判断当前已经添加的牛数量是否满足要求。

本题解析所用的编程语言:Java

完整且正确的编程代码

import java.util.*;


public class Solution {
    public static ArrayList<ArrayList<Integer>> lists = new
    ArrayList<ArrayList<Integer>>();
    public int[][] combine (int n, int k) {
        backTracking(1, new ArrayList<>(), n, k);

        int[][] ans = new int[lists.size()][k];
        for (int i = 0; i < lists.size(); i++) {
            for (int j = 0; j < k; j++) {
                ans[i][j] = lists.get(i).get(j);
            }
        }

        return ans;
    }

    void backTracking(int index, List<Integer> list, int n, int k) {
        for (int i = index; i <= n; i++) {
            list.add(i);
            if (list.size() == k) {
                lists.add(new ArrayList<>(list));
            } else {
                backTracking(i + 1, list, n, k);
            }
            list.remove(list.size() - 1);
        }

    }
}