C++实现LeetCode(Combinations 组合项)

[LeetCode] 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, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

这道题让求1到n共n个数字里k个数的组合数的所有情况，还是要用深度优先搜索DFS来解，根据以往的经验，像这种要求出所有结果的集合，一般都是用DFS调用递归来解。那么我们建立一个保存最终结果的大集合res，还要定义一个保存每一个组合的小集合out，每次放一个数到out里，如果out里数个数到了k个，则把out保存到最终结果中，否则在下一层中继续调用递归。可写出代码如下：

解法一：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> out;
        helper(n, k, 1, out, res);
        return res;
    }
    void helper(int n, int k, int level, vector<int>& out, vector<vector<int>>& res) {
        if (out.size() == k) {res.push_back(out); return;}
        for (int i = level; i <= n; ++i) {
            out.push_back(i);
            helper(n, k, i + 1, out, res);
            out.pop_back();
        }
    }
};

对于n = 5, k = 3, 处理的结果如下：

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

我们再来看一种递归的写法，此解法没用helper当递归函数，而是把本身就当作了递归函数，写起来十分的简洁，也是非常有趣的一种解法。这个解法用到了一个重要的性质 C(n, k) = C(n-1, k-1) + C(n-1, k)，这应该在我们高中时候学排列组合的时候学过吧，博主也记不清了。总之，翻译一下就是，在n个数中取k个数的组合项个数，等于在n-1个数中取k-1个数的组合项个数再加上在n-1个数中取k个数的组合项个数之和。这里博主就不证明了，因为我也不会，就直接举题目中的例子来说明吧：

C(4, 2) = C(3, 1) + C(3, 2)

我们不难写出 C(3, 1) 的所有情况：[1], [2], [3]，还有 C(3, 2) 的所有情况：[1, 2], [1, 3], [2, 3]。我们发现二者加起来为6，正好是 C(4, 2) 的个数之和。但是我们仔细看会发现，C(3, 2)的所有情况包含在 C(4, 2) 之中，但是 C(3, 1) 的每种情况只有一个数字，而我们需要的结果k=2，其实很好办，每种情况后面都加上4，于是变成了：[1, 4], [2, 4], [3, 4]，加上C(3, 2) 的所有情况：[1, 2], [1, 3], [2, 3]，正好就得到了 n=4, k=2 的所有情况了。参见代码如下：

解法二：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if (k > n || k < 0) return {};
        if (k == 0) return {{}};
        vector<vector<int>> res = combine(n - 1, k - 1);
        for (auto &a : res) a.push_back(n);
        for (auto &a : combine(n - 1, k)) res.push_back(a);
        return res;
    }
};

我们再来看一种迭代的写法，也是一种比较巧妙的方法。这里每次先递增最右边的数字，存入结果res中，当右边的数字超过了n，则增加其左边的数字，然后将当前数组赋值为左边的数字，再逐个递增，直到最左边的数字也超过了n，停止循环。对于n=4, k=2时，遍历的顺序如下所示：

0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop 

解法三：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> out(k, 0);
        int i = 0;
        while (i >= 0) {
            ++out[i];
            if (out[i] > n) --i;
            else if (i == k - 1) res.push_back(out);
            else {
                ++i;
                out[i] = out[i - 1];
            }
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(Combinations 组合项)的文章就介绍到这了,更多相关C++实现Combinations 组合项内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(35.搜索插入位置)

    [LeetCode] 35. Search Insert Position 搜索插入位置 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

    [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • C++实现LeetCode(32.最长有效括号)

    [LeetCode] 32. Longest Valid Parentheses 最长有效括号 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid

  • C++实现LeetCode(46.全排列)

    [LeetCode] 46. Permutations 全排列 Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题是求全排列问题,给的输入数组没有重复项,这跟之前的那道 Combinations 和类似,解法基本相同

  • C++实现LeetCode(Combinations 组合项)

    [LeetCode] 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, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 这道题让求1到n共n个数字里k个数的组合数的所有情况,还是要用深度优先搜索D

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(39.组合之和)

    [LeetCode] 39. Combination Sum 组合之和 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may b

  • Java实现LeetCode（组合总和）

    leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合.  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [   [7],   [2,2,3

  • C#常用数据结构和算法总结

    C#常用数据结构和算法总结

    1.数据 数据(Data)是外部世界信息的载体, 是能够被计算机识别,加工,存储的.在现实生活中也就是我们的产品原材料. 计算机中的数据包括数值数据,图片,影音资料等. 2. 数据元素和数据项 数据元素(Data Element)是数据的基本单位,在计算机处理的过程中通常是作为一个整体来作为处理的. 数据项(Data Item):一个数据元素通常由一个或多个数据项组成. 比如数据库表:(Student),它有Id,Name,Sex,Age,Address等字段,而这张表又有多行数据.我们通常将这

  • JavaScript 核心参考教程 RegExp对象

    正则表达式的直接量字符字符 匹配字母数字字符 本身\o NUL字符(\u0000)\t 制位表(\u0009)\n 换行符(\u000A)\v 垂直制位表(\u000B)\f 换页符(\u000C)\r 回车(\u000D)\xnn 由十六进制数nn指定的拉丁字符,例如\u0A等价于\n\uxxxx 由十六进制数xxxx指定的Unicode字符,例如\u0009等价于\t\cX 控制字符X,例如,\cJ等价于\n 正则表达式的字符类字符 匹配[...] 位于括号内的任意字符[^...] 不在括号

  • C++中结构体的类型定义和初始化以及变量引用

    C++中结构体的类型定义和初始化以及变量引用

    C++结构体类型的定义和初始化 有时需要将不同类型的数据组合成一个有机的整体,以供用户方便地使用.这些组合在一个整体中的数据是互相联系的.例如,一个学生的学号.姓名.性别.年龄.成绩.家庭地址等项,都是这个学生的属性,见图 可以看到学号(num).姓名(name).性别(sex).年龄(age).成绩(score ).地址(addr)是与姓名为"Li Fun"的学生有关的.如果在程序中将num,name,sex,age,score,addr分别定义为互相独立的变量,就难以反映出它们之间

  • 手撸一个 spring-boot-starter的全过程

    手撸一个 spring-boot-starter的全过程

    我们使用 Spring Boot,基本上都是沉醉在它 Stater 的方便之中.Starter 为我们带来了众多的自动化配置,有了这些自动化配置,我们可以不费吹灰之力就能搭建一个生产级开发环境,有的小伙伴会觉得这个 Starter 好神奇呀!其实 Starter 也都是 Spring + SpringMVC 中的基础知识点实现的,接下来带大家自己来撸一个 Starter ,慢慢揭开 Starter 的神秘面纱! 核心知识 其实 Starter 的核心就是条件注解 @Conditional ,当

  • Python使用combinations实现排列组合的方法

    好久没有写博客了!昨天小牛在上海举办了牛友见面会,现场优惠还是比较大,心仪已久加上一时脑热就入手了.以为会有多么开心,其实目前最大的感受就是焦虑!担心电动车被偷,担心电池被偷,担心路上突然被交警叔叔拦下!我想,直到我的小牛真的被偷的那天,这种焦虑才会随之消失.唉,要说这样的焦虑怎么来的,我只能呵呵了:) 下面步入正题: 今天在帮我们家王博处理专利数据的时候,需要对专利数据中的城市和专利主体的合作关系数量进行统计.一项专利其写作主体可能由两个或两个以上主体参与,各个主体又分属不同或者相同的城市,对

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

随机推荐