Leetcode組合解決方案


難度級別
經常問 土磚 亞馬遜 蘋果 Facebook 谷歌 Microsoft微軟 雅虎
回溯

組合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是指二項式係數。