美文网首页
LeetCode-077-组合

LeetCode-077-组合

作者: 醉舞经阁半卷书 | 来源:发表于2021-11-04 13:19 被阅读0次

    组合

    题目描述:给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

    你可以按 任何顺序 返回答案。

    示例说明请见LeetCode官网。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/combinations/
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解法一: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();
            }
        }
    }
    

    【每日寄语】 别害怕顾虑,想到就去做,这世界就是这样,当你把不敢去实现梦想的时候梦想就会离你越来越远,当你勇敢地去追梦的时候,全世界都会来帮你。

    相关文章

      网友评论

          本文标题:LeetCode-077-组合

          本文链接:https://www.haomeiwen.com/subject/feqkzltx.html