[Leetcode] Combinations 组合数

omgdog 发布于2019-08-14 12:31 / 2168人阅读

摘要：回溯法复杂度时间空间思路通过深度优先搜索，回溯出所有可能性即可。而递归的条件是当或者时，返回一个空列表。注意当返回的是空列表时，要加一个空列表进去，否则循环会被跳过代码加入一个空列表，防止跳过循环

Combinations

Given two integers n and k, return all possible ombinations of k numbers out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

回溯法 复杂度

时间 O(N) 空间 O(K)

思路

通过深度优先搜索，回溯出所有可能性即可。

代码

public class Solution {
    
    List> res = new ArrayList>();
    
    public List> combine(int n, int k) {
        dfs(1, k, n, new ArrayList());
        return res;
    }
    
    private void dfs(int start, int k, int n, List tmp){
        // 当已经选择足够数字时，将tmp加入结果
        if(k == 0){
            res.add(new ArrayList(tmp));
        }
        // 每一种选择数字的可能
        for(int i = start; i <= n; i++){
            tmp.add(i);
            dfs(i + 1, k - 1, n, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

公式法 复杂度

时间 O(N) 空间 O(N)

思路

在数学中，组合数有这么一个性质
$$ C_{n}^{k}=C_{n-1}^{k-1}cup n+C_{n-1}^{k}$$
所以，我们可以分别求出C(n-1,k-1)和C(n-1,k)，并将前者都加上n，最后将两个结果和到一起，就是C(n,k)。而递归的Base条件是当n=0,k=0或者n 注意

当C(n-1,k-1)返回的是空列表时，要加一个空列表进去，否则for循环会被跳过

代码

public class Solution {
    public List> combine(int n, int k) {
        // Recursion: C(n, k) = C(n-1, k-1) U n + C(n-1, k)
        // Base: C(0, k) C(n, 0) n < k ---> empty
        List> res = new LinkedList>();
        if(n < k || n == 0 || k == 0){
            return res;
        }
        // C(n-1, k-1) U n
        List> temp = combine(n-1, k-1);
        List> part1 = new LinkedList>();
        // 加入一个空列表，防止跳过for循环
        if(temp.isEmpty()){
            List list = new LinkedList();
            temp.add(list);
        }
        for(List list : temp){
            list.add(n);
            part1.add(list);
        }
        // C(n-1, k)
        List> part2 = combine(n-1, k);
        res.addAll(part1);
        res.addAll(part2);
        return res;
    }
}

GPU云服务器云服务器递归组合数 php遍历数组合并 java组合数并显示如何用c语言求组合数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64529.html

[Leetcode] Combination Sum 组合数之和

摘要：深度优先搜索复杂度时间空间递归栈空间思路因为我们可以任意组合任意多个数，看其和是否是目标数，而且还要返回所有可能的组合，所以我们必须遍历所有可能性才能求解。这题是非常基本且典型的深度优先搜索并返回路径的题。本质上是有限深度优先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...

GitCafe 2019-08-14 12:31 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
leetcode77. Combinations

摘要：再在前一种情况下继续下一轮的遍历，并将结果添加到队列末尾。思路二递归其实，通过递归的方法我们也可以在前一轮的基础上进行下一轮的计算。题目要求 Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2...

garfileo 2019-08-15 10:43 评论0 收藏0
leetcode-93-Restore IP Addresses

摘要：题目描述题目理解将一段字符广度搜索截取，分别有种组合形式，添加限制条件，过滤掉不适合的组合元素。长度，大小，首字母应用如果进行字符串的子元素组合穷举，可以应用。所有的循环，利用到前一个状态，都可以理解为动态规划的一种分支题目描述：Given a string containing only digits, restore it by returning all possible va...

wmui 2019-07-31 11:11 评论0 收藏0
leetcode 17 Letter Combinations of a Phone Number

摘要：而按键和字母的对应关系如上图。这将成为下一次操作的前序字符串。对于每一个不同的前序字符串，我们都要在其后面分别加上当前键所表示的不同字符，再将获得的结果字符串加入里面。题目详情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...

sean 2019-08-15 14:39 评论0 收藏0