LeetCode-077-组合 LeetCode-077-组合

组合

题目描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：dfs（深度优先遍历）

声明2个全局变量分别为结果集(result)和当前路径(path)，添加一个深度优先遍历的方法，该方法具体逻辑如下：

当k=0时，即当前路径已经有k个数了，说明当前路径符合条件，添加到结果集中；

然后遍历从1开始的数，递归调用dfs方法，调用完之后将当前路径的最后一个数从路径中去掉。

【LeetCode-077-组合】最后，返回结果集即为所有符合条件的组合。

import java.util.ArrayList; import java.util.List; public class LeetCode_077 { /** * 结果集 */ private static List> result = new ArrayList<>(); /** * 当前的路径 */ private static List path = new ArrayList<>(); /** * dfs * * @param n 总共有n个数 * @param k k个数的组合 * @return */ public static List> combine(int n, int k) { // 递归方法入口 dfs(1, n, k); // 返回结果集 return result; }/** * 深度优先搜索 * * @param u 路径的起点 * @param n 总共有n个数 * @param k 还剩多少个值达到原定的k个数 */ private static void dfs(int u, int n, int k) { if (k == 0) { /** * 当k等于0时，表示已经有k个数了，满足条件放入结果集中 */ result.add(new ArrayList<>(path)); return; }for (int i = u; i <= n - k + 1; i++) { /** * 将当前的数添加到路径中 */ path.add(i); dfs(i + 1, n, k - 1); path.remove(path.size() - 1); } }public static void main(String[] args) { for (List integers : combine(4, 2)) { for (Integer integer : integers) { System.out.print(integer + " "); } System.out.println(); } } }