LeetCode 77. 组合（Combinations）

发布时间：2020-12-14 03:47:59 所属栏目：大数据来源：网络整理

导读：题目描述 ? 给定两个整数? n ?和? k ，返回 1 ...? n? 中所有可能的? k ?个数的组合。示例: 输入:?n = 4,k = 2输出:[ [2,4],[3,[2,3],[1,2],] ? 解题思路 ? 回溯法，每次遍历到一个元素分为放入与不放入集合两种情况，若集合长度为k，则加入到结果中。 ? 代

题目描述

给定两个整数?n?和?k，返回 1 ...?n?中所有可能的?k?个数的组合。

示例:

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

解题思路

回溯法，每次遍历到一个元素分为放入与不放入集合两种情况，若集合长度为k，则加入到结果中。

代码

 1 class Solution {
 2 public:
 3     vector<vector<int>> combine(int n,int k) {
 4         vector<vector<int>> res;
 5         vector<int> nums,temp;
 6         for(int i = 0; i < n; i++)
 7             nums.push_back(i + 1);
 8         cmb(n,k,0,nums,temp,res);
 9         return res;
10     }
11     void cmb(int n,int k,int idx,vector<int> nums,vector<int> &temp,vector<vector<int>> &res){
12         if(k && temp.size() == k)
13             res.push_back(temp);
14         else if(idx < n){
15             temp.push_back(nums[idx]);
16             cmb(n,idx + 1,res);
17             temp.pop_back();
18             cmb(n,res);
19         }
20     }
21 };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!