LeetCode每日一题：combinations

问题描述

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

问题分析

这题不能直接穷举，有k层循环会直接超时的，我们可以采用dfs来遍历，用depth来表示第一个数，那么第二个数是在n-depth中寻找，由于题目对排列顺序没有要求，dfs可以满足要求

代码实现

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        getCombine(1, n, k, list, result);
        return result;
    }

    private void getCombine(int depth, int n, int k, ArrayList<Integer> list,
                            ArrayList<ArrayList<Integer>> result) {
        if (k == 0) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = depth; i <= n; i++) {
            list.add(i);
            getCombine(i + 1, n, k - 1, list, result);//递归遍历depth
            list.remove(list.size() - 1);
        }
    }