题解 | #牛棚分组#

题目考察的知识点

考察回溯算法

题目解答方法的文字分析

其实就是利用回溯算法进行深度优先搜索。这里通过list添加删除元素，检查集合个数控制排列，不断递归回溯找到所有组合

本题解析所用的编程语言

使用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);
        }

    }
}