# 总和可被m整除的子集

## 使用案列

array = {1, 2, 4}
m = 3
True

## 代码

### 子集的C ++代码，其和可被m整除

#include<bits/stdc++.h>
using namespace std;

bool findSubsetDivisibleByM(int arr[], int n, int m)
{
// because of piegonhole principle
if (n > m)
return true;

// this will work as dp array for all elements until the last element
bool dp[m]; memset(dp, false, m);

for (int i=0; i<n; i++)
{
// this will work as our current dp array
bool tmp[m]; memset(tmp,false,m);

// we will add the current element to all possible subset sum
// until now and then take the mod of the sum and will keep
// on filling the current dp array(tmp)
for (int j=0; j<m; j++)
{
// if the dp table until the last element has subset sum = j
if (dp[j] == true)
{
if (dp[(j+arr[i]) % m] == false)
// fill the current dp table(tmp array)
tmp[(j+arr[i]) % m] = true;
}
}

// now just fill the original dp array
for (int j=0; j<m; j++)
if (tmp[j] == true)
dp[j] = true;
// fill the dp array considering you have subset made of only current element
dp[arr[i]%m] = true;
}

return dp[0];
}

int main(){
// Number of elements
int n;cin>>n;
// Number which should divide the subset
int m;cin>>m;
// array to store non-negative numbers
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
bool can = findSubsetDivisibleByM(a, n, m);
if(can == true)
cout<<"There exists a subset having sum divisible by m";
else
cout<<"There does not exist any subset having sum divisible by m";
}
3 3
1 2 4
There exists a subset having sum divisible by m

### 子集的Java代码，其总和可被m整除

import java.util.*;
class Main{

static boolean findSubsetDivisibleByM(int arr[], int n, int m)
{
// because of piegonhole principle
if (n > m)
return true;

// this will work as dp array for all elements until the last element
boolean dp[] = new boolean [m];
for(int i=0;i<m;i++)
dp[i] = false;

for (int i=0;i<n; i++)
{
// this will work as our current dp array
boolean tmp[] = new boolean[m];
for(int j=0;j<m;j++)
tmp[j] = false;
// we will add the current element to all possible subset sum
// until now and then take the mod of the sum and will keep
// on filling the current dp array(tmp)
for (int j=0; j<m; j++)
{
// if the dp table until the last element has subset sum = j
if (dp[j] == true)
{
if (dp[(j+arr[i]) % m] == false)
// fill the current dp table(tmp array)
tmp[(j+arr[i]) % m] = true;
}
}

// now just fill the original dp array
for (int j=0; j<m; j++)
if (tmp[j] == true)
dp[j] = true;
// fill the dp array considering you have subset made of only current element
dp[arr[i]%m] = true;
}

return dp[0];
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
// Number of elements
int n = sc.nextInt();
int m = sc.nextInt();
// array to store non-negative numbers
int a[] = new int[n];
for(int i=0;i<n;i++)
a[i] = sc.nextInt();
boolean can = findSubsetDivisibleByM(a, n, m);
if(can == true)
System.out.println("There exists a subset having sum divisible by m");
else
System.out.println("There does not exist any subset having sum divisible by m");
}
}
3 3
1 2 4
There exists a subset having sum divisible by m

## 复杂度分析

### 时间复杂度

O（M ^ 2），因为我们仅在n <= m时才需要解决问题。 因此，n的上限为m。 因此，时间复杂度是多项式。

### 空间复杂度

O（M）， 因为dp阵列所需的空间是线性的。 仅需要空间来存储dp表，因此空间复杂度是线性的。