하위 집합 Leetcode

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 ByteDance Facebook 구글 Microsoft 신탁
알고리즘 배열 역 추적 비트 비트 조작 비트 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 50

부분 집합 Leetcode 문제에서 우리는 고유 한 정수 집합, 숫자, 모든 부분 집합 인쇄 (파워 집합)를 제공했습니다.

참고 : 솔루션 세트에는 중복 서브 세트가 없어야합니다.

배열 A는 일부 (아마도 XNUMX 또는 모든) 요소를 삭제하여 B에서 a를 얻을 수있는 경우 배열 B의 하위 집합입니다.

입력:

[1, 2, 3]

출력:

[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

접근 방식 1 : 비트 조작을 사용하는 반복 솔루션

n 개 요소 집합의 각 하위 집합은 0 ~ 2n-1 사이의 정수에 해당하는 n 비트 시퀀스로 표현 될 수 있습니다. 비트 시퀀스의 요소는 하위 집합에 포함 된 요소를 나타냅니다.

암호알고리즘

  1. 선언 정렬 모든 하위 집합을 저장할 벡터 "ans"의.
  2. nums_array의 크기를 나타내는 변수 n을 초기화합니다.
  3. 0 ~ 2 범위에서 I에 대한 루프 실행n-1
    1. 현재 하위 집합을 저장할 배열 "temp"를 초기화합니다.
    2. 0 ~ n-1 범위에서 j에 대해 루프 실행
      1. I의 j 번째 비트가 설정되면 nums [i]를 임시 배열에 추가합니다.
    3. "ans"에 "temp"배열 추가
  4. 최종 ans 배열을 인쇄합니다.

모든 서브 세트 인쇄 구현

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (nums.size())); i++)
    {
        vector<int> temp;
        for (int j = 0; j < nums.size(); j++)
        {
            if (i & (1 << j))
            {
                temp.push_back(nums[j]);
            }
        }
        ans.push_back(temp);
    }
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

모든 서브 세트 인쇄를위한 복잡성 분석

시간 복잡성

두 개의 중첩 루프를 실행합니다. 하나는 범위 2 ^ n이고 다른 하나는 범위 n입니다. 따라서 최종 시간 복잡도는 O (2 ^ n * n)입니다.

공간 복잡성

2 ^ n-1 개의 하위 집합이 있으며 모든 하위 집합에 대해 평균 O (n) 공간이 필요하므로 총 공간 복잡도는 O (2 ^ n * n)입니다.

최적화 할 수 있습니까?

예, 역 추적을 사용하여 최적화 할 수 있습니다. 방법을 살펴 보겠습니다!

접근 방식 2 : 역 추적을 사용하는 재귀 솔루션

nums 배열을 반복하고 각 위치에 대해 i 번째 요소를 가져 오거나 건너 뛰는 두 가지 선택 사항이 있습니다.

암호알고리즘

  1. 인수, 최종 답 배열, 현재 하위 집합 배열, 입력 배열 및 nums 배열의 현재 요소를 가리키는 변수 "인덱스"를 사용하는 함수를 만듭니다.
  2. 기본 조건 : "인덱스"가 nums 배열의 크기와 같으면 더 이상 nums 배열을 탐색 할 수 없기 때문에 현재 하위 집합 배열을 최종 답변에 추가합니다.
  3. 이제 두 가지 선택이 있습니다
    1. 현재 요소를 건너 뛰고 index + 1을 사용하여 재귀 함수를 호출하면 다른 모든 인수는 동일하게 유지됩니다.
    2. 현재 요소를 현재 하위 집합에 추가하고 인덱스 +1 및 기타 인수를 사용하여 재귀 함수를 호출합니다. 재귀 함수를 호출 한 후 현재 하위 집합에서 마지막 요소를 제거하여 역 추적 단계를 수행합니다.
  4. 최종 답을 인쇄하십시오.

예를 들어 이해

입력 배열을 봅시다. nums = [1,2,3]

그런 다음 재귀 트리는 다음과 같습니다.

하위 집합 Leetcode

위의 트리에서 Subset (i)는 i가 현재 인덱스를 나타내는 재귀 함수입니다.

모든 서브 세트 인쇄 구현

하위 집합 Leetcode 용 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void subsets(vector<vector<int>> &ans, vector<int> &temp, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        ans.push_back(temp);
        return;
    }
    subsets(ans, temp, nums, i + 1);
    temp.push_back(nums[i]);
    subsets(ans, temp, nums, i + 1);
    temp.pop_back();
    return;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    vector<int> temp;
    subsets(ans, temp, nums, 0);
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

하위 집합 Leetcode 용 JAVA 프로그램

import java.util.*; 
public class Main
{
    static List<List<Integer>> res;
    public static void subsets(int[] nums,int index,List<Integer> list){
        if(index==nums.length-1){
            res.add(new ArrayList<Integer>(list));
            list.add(nums[index]);
            res.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        subsets(nums,index+1,list);
        list.add(nums[index]);
        subsets(nums,index+1,list);
        list.remove(list.size()-1);
    }
  public static void main(String[] args) {
      res = new ArrayList<>();
      int[] nums={2, 3, 4};
      List<Integer> list = new ArrayList<Integer>();
      subsets(nums, 0, list);
      for(List<Integer> subset:res){
          for(int i: subset){
              System.out.print(i+", ");
          }
            System.out.println();
      }
  }
}

4, 
3, 
3, 4, 
2, 
2, 4, 
2, 3, 
2, 3, 4, 

부분 집합 Leetcode에 대한 복잡성 분석

시간 복잡성

모든 인덱스에 대해 2 개의 재귀 호출을 만들고 n 개의 요소가 있으므로 총 시간 복잡도는 O (2 ^ n)입니다.

공간 복잡성

2 ^ n-1 개의 하위 집합이 있으며 모든 하위 집합에 대해 평균 O (n) 공간이 필요하므로 총 공간 복잡도는 O (2 ^ n * n)입니다.

참조

코멘트를 남겨

Translate »