LeetCode 组合【dfs】

刺骨的言语ヽ痛彻心扉 2022-09-15 11:52 129阅读 0赞

# 1 组合 #

给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。

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

示例 1：

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

示例 2：

输入：n = 1, k = 1
    输出：[[1]]

提示：

1 <= n <= 20
    1 <= k <= n

# 2 解题 #

public List<List<Integer>> combine(int n, int k) { 
            List<List<Integer>> rs = new ArrayList<>();
            return dfs(rs, new LinkedList<>(), n, k, 1);
        }
    
    
        private List<List<Integer>> dfs(List<List<Integer>> rs, LinkedList<Integer> currentList, int n, int k, int index) { 
            if (currentList.size() == k) { 
                rs.add(new ArrayList<>(currentList));
            } else { 
                for (int i = index; i <= n; i++) { 
                    //剪枝
                    if (currentList.size() + n - i + 1 >= k) { 
                        currentList.addLast(i);
                        dfs(rs, currentList, n, k, i + 1);
                        currentList.removeLast();
                    }
                }
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ef2ec47a9dcc47ff89ac203b39c1456c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode——DFS

DFS -------------------- 目录 1. DFS 2. 查找最大的连通面积 3. 矩阵中的连通分量数目 4. 好友关系的连通分量数目

谁践踏了优雅/ 2023年06月19日 04:20/ 0 赞/ 100 阅读

相关【leetcode.77】组合

一、题目描述给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。示例: > 输入: n = 4, k = 2 > 输出: > \

梦里梦外;/ 2022年12月09日 15:56/ 0 赞/ 237 阅读

相关 [Leetcode][第39题][JAVA][组合总和][回溯][dfs][剪枝]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

向右看齐/ 2022年12月05日 05:11/ 0 赞/ 203 阅读

相关网格DFS LeetCode

岛屿问题(DFS) [200. 岛屿数量][200.] 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围

雨点打透心脏的1/2处/ 2022年10月26日 03:54/ 0 赞/ 168 阅读

相关 LeetCode 组合【dfs】

1 组合给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。示例 1：输入：n = 4

刺骨的言语ヽ痛彻心扉/ 2022年09月15日 11:52/ 0 赞/ 130 阅读

相关代码填空：组合数字(DFS)

右侧代码是将 6 个整数按照任意顺序组合到一起，计算能组合出的最大数字。例如：4123，25，66 组合到一起就是 66412325。请阅读程序补全代码，实现

亦凉/ 2022年06月18日 09:14/ 0 赞/ 189 阅读

相关组合数(dfs)

给出一个正整数N，从集合\{1,2,3..N\} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整数T,代表T组测试数据。接下来T行

淡淡的烟草味﹌/ 2022年05月15日 01:11/ 0 赞/ 243 阅读

相关 LeetCode77. 组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。示例: 输入: n = 4, k = 2 输出: [ [

迷南。/ 2022年05月12日 06:20/ 0 赞/ 217 阅读

相关 LeetCode 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例: nums = [1, 2, 3] target = 4

ゞ浴缸里的玫瑰/ 2022年04月08日 09:47/ 0 赞/ 231 阅读

相关 ✔[77]组合（回溯，DFS）

//给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 // // 示例: // // 输入: n = 4, k = 2 //输出:

约定不等于承诺〃/ 2021年06月22日 15:38/ 0 赞/ 488 阅读