组合

题目形容：给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。

你能够按 任何程序 返回答案。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

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

申明2个全局变量别离为后果集(result)和以后门路(path)，增加一个深度优先遍历的办法，该办法具体逻辑如下：

  • 当k=0时，即以后门路曾经有k个数了，阐明以后门路符合条件，增加到后果集中；
  • 而后遍历从1开始的数，递归调用dfs办法，调用完之后将以后门路的最初一个数从门路中去掉。

最初，返回后果集即为所有符合条件的组合。

import java.util.ArrayList;import java.util.List;public class LeetCode_077 {    /**     * 后果集     */    private static List<List<Integer>> result = new ArrayList<>();    /**     * 以后的门路     */    private static List<Integer> path = new ArrayList<>();    /**     * dfs     *     * @param n 总共有n个数     * @param k k个数的组合     * @return     */    public static List<List<Integer>> 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<Integer> integers : combine(4, 2)) {            for (Integer integer : integers) {                System.out.print(integer + " ");            }            System.out.println();        }    }}
【每日寄语】 别胆怯顾虑，想到就去做，这世界就是这样，当你把不敢去实现幻想的时候幻想就会离你越来越远，当你怯懦地去追梦的时候，全世界都会来帮你。