부분 집합 합계 Leetcode

난이도 중급
알고리즘 배열 코딩 동적 프로그래밍 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 92

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

부분 집합 합계 leetcode 문제는 주어진 정렬 크기 n의 a []. 한 부분 집합의 값의 합이 다른 부분 집합과 같도록 배열을 두 부분 집합으로 나눌 수 있는지 확인합니다. 가능하면 "Yes"를 인쇄하고 그렇지 않으면 "No"를 인쇄하십시오.

a[ ] = {2, 3, 5}
Yes

설명 : 첫 번째 요소와 두 번째 요소의 합은 세 번째 요소와 같습니다. 따라서 주어진 배열은 두 개의 하위 집합으로 나눌 수 있습니다.

a[ ] = {1, 2, 4, 9}
No

설명 : 배열이 동일한 합계를 갖도록 두 개의 하위 집합으로 나눌 수있는 가능한 조합은 없습니다.

재귀 적 방법

암호알고리즘

1. 크기 n의 배열 a []를 초기화합니다.
2. 배열을 가로 질러 주어진 배열 a []에있는 모든 요소의 합을 찾습니다. sum mod 2가 0이 아닌지 확인하고 false를 반환합니다.
3. 만들기 기능 그 합계가 전체 원래 배열의 합계의 절반과 같은 배열에 하위 집합이 있는지 확인합니다.
4. 마지막 요소를 포함하고 마지막 요소를 제외하여이 함수를 재귀 적으로 호출합니다.
5. 합계가 XNUMX이면 true를 반환합니다. 그렇지 않으면 합계가 XNUMX이 아니고 n이 XNUMX이면 false를 반환합니다.

Subset Sum Leetcode 구현

부분 집합 합계에 대한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
  
bool isEqualSum(int a[], int n, int sum){  
    if(sum == 0)  
        return true;  
    if(n == 0 && sum != 0)  
        return false;  
  
    if(a[n-1] > sum)  
       return isEqualSum(a, n-1, sum);  
  
    return isEqualSum(a, n-1, sum) ||  
        isEqualSum(a, n-1, sum-a[n-1]);  
}  
  
bool Partiion(int a[], int n){  
    int sum = 0;  
    for(int i=0; i<n; i++)  
    sum += a[i];  
  
    if(sum%2 != 0)  
        return false;  
  
    return isEqualSum (a, n, sum/2);  
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

부분 집합 합계에 대한 Java 코드

import java.io.*; 
  
class equalSum{ 
    static boolean isEqualSum(int a[], int n, int sum){ 
        if(sum == 0) 
            return true; 
        if(n == 0 && sum != 0) 
            return false; 
  
        if(a[n-1] > sum) 
            return isEqualSum(a, n-1, sum); 
  
        return isEqualSum(a, n-1, sum) || 
               isEqualSum(a, n-1, sum-a[n-1]); 
    } 
  
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        for(int i = 0; i < n; i++) 
            sum += a[i]; 
  
        if (sum%2 != 0) 
            return false; 
  
        return isEqualSum(a, n, sum/2); 
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

Subset Sum Leetcode에 대한 복잡성 분석

시간 복잡성

각 문제는 두 개의 작은 하위 문제로 나뉩니다. 그것은 알고리즘이 O (2n) 시간 복잡도, 여기서 n은 주어진 배열 a []에있는 정수의 수입니다.

공간 복잡성

O (1), 우리는 일정한 추가 공간을 사용했기 때문입니다.

동적 프로그래밍 방법

암호알고리즘

1. 크기 n의 배열 a []를 초기화합니다.
2. 배열을 탐색하고 모든 요소의 합계를 찾습니다. sum mod 2가 0이 아닌지 확인하고 false를 반환합니다.
3. 2D 배열을 만듭니다.
4. 첫 번째 행을 true로 업데이트하고 각 행의 첫 번째 열을 false로 업데이트합니다.
5. 순회를 시작하고 j-1까지 원래 배열의 하위 집합의 합계가 i와 같으면 part [] []를 true로 업데이트합니다. 그렇지 않으면 거짓.
6. 부분적으로 마지막 부울 값을 반환합니다.

Subset Sum Leetcode 구현

부분 집합 합계에 대한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
  
bool Partiion(int a[], int n){  
    int sum = 0; 
    int i, j; 

    for(i=0; i<n; i++) 
        sum += a[i]; 

    if(sum%2 != 0) 
        return false; 

    bool part[sum / 2 + 1][n + 1]; 

    for (i = 0; i <= n; i++) 
        part[0][i] = true; 

    for (i = 1; i <= sum/2; i++) 
        part[i][0] = false; 

    for(i=1; i<=sum/2; i++){ 
        for(j=1; j<=n; j++){ 
            part[i][j] = part[i][j-1]; 
            if(i >= a[j-1]) 
                part[i][j] = part[i][j] || 
                             part[i - a[j-1]][j-1]; 
        } 
    }
    return part[sum/2][n];   
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

부분 집합 합계에 대한 Java 코드

import java.io.*; 
  
class equalSum{ 
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        int i, j; 
  
        for(i=0; i<n; i++) 
            sum += a[i]; 
  
        if(sum%2 != 0) 
            return false; 
  
        boolean part[][]=new boolean[sum/2+1][n+1]; 
  
        for (i = 0; i <= n; i++) 
            part[0][i] = true; 
  
        for (i = 1; i <= sum/2; i++) 
            part[i][0] = false; 
  
        for(i=1; i<=sum/2; i++){ 
            for(j=1; j<=n; j++){ 
                part[i][j] = part[i][j-1]; 
                if(i >= a[j-1]) 
                    part[i][j] = part[i][j] || 
                                 part[i - a[j-1]][j-1]; 
            } 
        }
        return part[sum/2][n];  
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

Subset Sum Leetcode에 대한 복잡성 분석

시간 복잡성

O (합 * n) 여기서 n은 주어진 배열 a []에있는 정수의 수이고 합계는 주어진 배열 a []에있는 모든 요소의 합입니다.

공간 복잡성

O (합 * n) sum * n 추가 공간을 사용했기 때문입니다.

참조

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