부분 집합 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 비트 시퀀스로 표현 될 수 있습니다. 비트 시퀀스의 요소는 하위 집합에 포함 된 요소를 나타냅니다.
암호알고리즘
- 선언 정렬 모든 하위 집합을 저장할 벡터 "ans"의.
- nums_array의 크기를 나타내는 변수 n을 초기화합니다.
- 0 ~ 2 범위에서 I에 대한 루프 실행n-1
- 현재 하위 집합을 저장할 배열 "temp"를 초기화합니다.
- 0 ~ n-1 범위에서 j에 대해 루프 실행
- I의 j 번째 비트가 설정되면 nums [i]를 임시 배열에 추가합니다.
- "ans"에 "temp"배열 추가
- 최종 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 번째 요소를 가져 오거나 건너 뛰는 두 가지 선택 사항이 있습니다.
암호알고리즘
- 인수, 최종 답 배열, 현재 하위 집합 배열, 입력 배열 및 nums 배열의 현재 요소를 가리키는 변수 "인덱스"를 사용하는 함수를 만듭니다.
- 기본 조건 : "인덱스"가 nums 배열의 크기와 같으면 더 이상 nums 배열을 탐색 할 수 없기 때문에 현재 하위 집합 배열을 최종 답변에 추가합니다.
- 이제 두 가지 선택이 있습니다
- 현재 요소를 건너 뛰고 index + 1을 사용하여 재귀 함수를 호출하면 다른 모든 인수는 동일하게 유지됩니다.
- 현재 요소를 현재 하위 집합에 추가하고 인덱스 +1 및 기타 인수를 사용하여 재귀 함수를 호출합니다. 재귀 함수를 호출 한 후 현재 하위 집합에서 마지막 요소를 제거하여 역 추적 단계를 수행합니다.
- 최종 답을 인쇄하십시오.
예를 들어 이해
입력 배열을 봅시다. nums = [1,2,3]
그런 다음 재귀 트리는 다음과 같습니다.
위의 트리에서 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)입니다.
