Đếm các tập con thỏa mãn điều kiện đã cho trong C ++

Cho một mảng số và một số nguyên x làm đầu vào. Mục đích là tìm tất cả các tập con của arr [] sao cho các phần tử riêng lẻ của tập đó cũng như tổng của chúng chia hết cho x.

Ví dụ

Đầu vào

arr[] = {1,2,3,4,5,6} x=3

Đầu ra

Count of subsets that satisfy the given condition :3

Giải thích

The subsets will be:
[3], [6], [3,6]

Đầu vào

arr[] = {1,2,3,4,5,6} x=4

Đầu ra

Count of subsets that satisfy the given condition :1

Giải thích

The subsets will be:
[4]

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ đếm các phần tử của arr [] chia hết cho x và sau đó trả về 2 ^count −1 là số lượng tập con được yêu cầu.

• Lấy một mảng số nguyên arr [].

• Lấy x làm đầu vào.

• Hàm đếm (int arr [], int n, int x) nhận một mảng và x và trả về số lượng các tập con thỏa mãn điều kiện đã cho.

• Nếu x là 1 thì nó sẽ chia tất cả các phần tử, vì vậy trả về

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of sub−sets that satisfy the given condition are: 7