By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:


输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

1.1、解题思路

类似于求数组中的全部子序列，只不过这里加了判断条件，提前出去了

1.2、算法

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();

    dfs(1, res, linkedList, n, k);
    return res;
}

public void dfs(int index, List<List<Integer>> res, LinkedList<Integer> linkedList, int n, int k ) {
    if (linkedList.size() == k) {
        res.add(new ArrayList<>(linkedList));
        return;
    }

    for (int i = index; i <= n; i++) {
        linkedList.add(i);
        dfs(i + 1, res, linkedList, n, k);
        linkedList.removeLast();
    }
}

1.3、测试


@Test
public void test(){
    System.out.println(combine(4 , 2));
}

​

ContactAuthor