조합 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple Facebook 구글 Microsoft Yahoo
알고리즘 역 추적 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 88

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 Combinations Leetcode Solution은 두 개의 정수, 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 솔루션에 대한 접근 방식

문제 Combinations Leetcode Solution은 처음 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

자바 코드

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는 이항 계수를 나타냅니다.

균열 시스템 설계 인터뷰
Translate »
1