숫자 배열과 정수 x가 입력으로 주어집니다. 목표는 해당 집합의 개별 요소와 그 합이 x로 완전히 나누어지도록 하는 arr[]의 모든 하위 집합을 찾는 것입니다.
예를 들어
입력
arr[] = {1,2,3,4,5,6} x=3 출력
Count of subsets that satisfy the given condition :3
설명
The subsets will be: [3], [6], [3,6]
입력
arr[] = {1,2,3,4,5,6} x=4 출력
Count of subsets that satisfy the given condition :1
설명
The subsets will be: [4]
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서는 x로 완전히 나눌 수 있는 arr[]의 요소를 계산한 다음 2 count 를 반환합니다. -1 필요한 부분집합 수로.
-
정수 배열 arr[]를 가져옵니다.
-
x를 입력으로 사용합니다.
-
count(int arr[], int n, int x) 함수는 배열과 x를 취해 주어진 조건을 만족하는 부분집합의 개수를 반환합니다.
-
x가 1이면 모든 요소를 나눕니다. 따라서 return
예시
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int sub_sets(int arr[], int size, int val){
int count = 0;
if (val == 1){
count = pow(2, size) − 1;
return count;
}
for (int i = 0; i < size; i++){
if (arr[i] % val == 0){
count++;
}
}
count = pow(2, count) − 1;
return count;
}
int main(){
int arr[] = { 4, 6, 1, 3, 8, 10, 12 }, val = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of sub−sets that satisfy the given condition are: "<<sub_sets(arr, size, val);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of sub−sets that satisfy the given condition are: 7