Leetcode组合解决方案


难度级别 中等
经常问 土砖 亚马逊 Apple Facebook 谷歌 微软 雅虎
回溯

组合Leetcode解决方案问题为我们提供了两个整数n和k。 告诉我们生成从1到n的n个元素中选出k个元素的所有序列。 我们将这些序列作为 排列。 让我们通过一些示例来更好地理解问题。

n = 4, k = 2
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

说明:输出显示了从前n个自然数中挑选k个元素的所有方法。 在此,数字的顺序无关紧要。 只有数字的集合才重要。

n = 1, k = 1
[[1]]

说明:在这里,因为我们只有一个元素。 我们还被告知要选择一个元素。 因此,输出为[[1]]。

组合Leetcode解决方案的方法

组合Leetcode解决方案问题只要求我们简单地生成从前n个自然数中挑选k个元素的所有序列。 因此,这只是生成所有可用于选择k个元素的nCk组合。 通常,使用递归来解决涉及序列生成的任务。 因此,我们尝试对问题进行递归处理。 并跟踪旨在存储此类组合的向量。

因此,我们从一个空向量开始。 我们将元素推入其中。 然后递归解决从剩余的n-1个元素中挑选k-1个元素的子问题。 通过这种方式,我们一直在减少问题,直到达到选择0个元素的问题为止。 发生这种情况时,我们将此临时向量推入我们的答案。 最后,此答案存储了从n个元素中挑选k个元素的所有序列。

Leetcode组合解决方案

组合代码Leetcode解决方案

C ++代码

#include <bits/stdc++.h>
using namespace std;

void rec(int i, int k, int n, vector<int>& cur, vector<vector<int>>& res){
    if(cur.size()==k) {
        res.push_back(cur);
    } else {
        for(int j=i;j<=n;j++) {
            cur.push_back(j);
            rec(j+1, k, n, cur, res);
            cur.pop_back();
        }
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> cur;
    rec(1, k, n, cur, res);
    return res;
}

int main(){
    vector<vector<int>> output = combine(4, 2);
    for(auto singleList: output){
        for(auto element: singleList)
            cout<<element<<" ";
        cout<<endl;
    }
}
1 2
1 3
1 4
2 3
2 4
3 4

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  static List<List<Integer>> res = new ArrayList<List<Integer>>();
  
    public static void rec(int i, int k, int n, ArrayList<Integer> cur){
        if(cur.size()==k) {
            res.add(new ArrayList(cur));
        } else {
            for(int j=i;j<=n;j++) {
                cur.add(j);
                rec(j+1, k, n, cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    
    public static List<List<Integer>> combine(int n, int k) {
        ArrayList<Integer> cur = new ArrayList<Integer>();
        rec(1, k, n, cur);
        return res;
    }

  public static void main (String[] args) throws java.lang.Exception{
    List<List<Integer>> res = combine(4, 2);
    System.out.println(res);
  }
}
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

复杂度分析

时间复杂度

O(k * nCk), 在此,nCk表示从n个元素中选取k个元素的二项式系数。

空间复杂度

O(nCk), 如上所述,这里的nCk是指二项式系数。